在某些问题中，例如排列，我们一个一个填充位置；而在其他问题如子集或划分中，我们基于已选择的元素继续前进。为什么这些问题在每一步之后移动的方式不同？

返回所有可能的排列：

class Solution {
  public List<List<Integer>> permute( int[] nums ) {
     List<List<Integer>> ans = new ArrayList<>();
     set( 0, nums, ans );
     return ans;
  }

  public void set( int ind, int nums[], 
                   List<List<Integer>> ans ) {
     if( ind == nums.length ) {
        // logic to return ans
        return; 
     }

     for( int i = ind; i < nums.length; i++ ) {
        swap( i, ind, nums );
        set( ind + 1, nums, ans ); // Why don’t we use i + 1 here?
        swap( i, ind, nums );
     }
  }

  public void swap( int i, int j, int arr[] ) {
     // swap logic
  }
}

返回字符串的回文分割：

class Solution {
  public List<List<String>> partition( String s ) {
     List<List<String>> ans = new ArrayList<>();
     List<String> ds = new ArrayList<>();
     partition( 0, ans, ds, s );
     return ans;
  }

  public void partition( int ind, List<List<String>> ans, 
                         List<String> ds, String s ) {
     if( ind == s.length() ) {
        // logic to return ans
        return; 
     }
     for( int i = ind; i < s.length(); i++ ) {
        if( ispalindrome( s, ind, i )) {
           ds.add( s.substring( ind, i + 1 ));
           partition( i + 1, ans, ds, s ); // here we did not use ind+1, why?
           ds.remove( ds.size() - 1 );
        }
     }   
  }
}

现在你能解释为什么在排列中，在 for 循环内调用递归时要使用 i+1？以及在回文分割中，在 for 循环内调用递归时要使用 ind+1 的原因。

解决方案

下面是我的理解：

permutations – ind 表示“我现在正在填充的是哪一个位置。”

（也就是说，我们不关心刚才使用的元素是什么，我们只关心位置 ind 现在已经被填充。因此下一次调用将转到 ind + 1（下一个位置）。在这里使用 i + 1 没有意义，因为 i 只是我们从剩余集合中选出的元素的索引，而不是一个位置。）

palindrome partitioning – ind 表示“我的下一次切割应该从字符串的哪里开始。”

（在我们从 ind 到 i 取出一个子串之后，下一次切割必须从该子串结束的地方紧接着开始，也就是 i + 1。使用 ind + 1 将是错误的——那样只会切出单个字符，无法取出更长的子串。）

所以：

我们必须看看 ind 在状态中代表的是什么。

• 如果你是在填充槽位（排列、N皇后问题） → ind + 1
• 如果你是在处理输入块（划分、子集、组合） → i + 1（其中 i 是你刚才取出的块的结束位置）