回溯算法递归参数选择：排列与回文分割的差异解析

核心思路差异：填充位置 vs 推进边界 #

回溯算法的递归参数设计完全取决于问题的目标：

• 排列问题：目标是生成所有元素的全排列，本质是逐个填充每个位置。每个位置（第0位、第1位……）需要选择一个未使用的元素，因此递归的核心是推进到下一个待填充的位置。
• 回文分割/子集问题：目标是基于原序列生成符合条件的子序列/分割结果，本质是基于已选元素推进处理边界。我们需要从当前未处理的起始位置开始，选择一段元素加入结果，然后递归处理剩余的未处理部分。

排列问题代码解析：为何用ind+1 #

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 ) {
        // 将当前nums数组转为列表加入ans
        List<Integer> temp = new ArrayList<>();
        for(int num : nums) temp.add(num);
        ans.add(temp);
        return; 
     }

     for( int i = ind; i < nums.length; i++ ) {
        swap( i, ind, nums );
        set( ind + 1, nums, ans ); // 此处用ind+1而非i+1
        swap( i, ind, nums );
     }
  }

  public void swap( int i, int j, int arr[] ) {
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
  }
}

这里的ind代表当前要填充的位置索引：

1. 循环中通过swap(i, ind)，把nums[i]放到当前待填充的ind位置，相当于为这个位置选定了元素。
2. 递归调用set(ind+1, ...)是因为：当前ind位置已经填充完成，接下来需要处理下一个位置（ind+1），和当前循环的i值无关——不管选了哪个元素填到ind位，下一个要处理的都是固定的下一个位置。
3. 如果误用i+1，会导致跳过中间的位置，无法生成完整的排列，逻辑完全错误。

回文分割问题代码解析：为何用i+1 #

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() ) {
        ans.add(new ArrayList<>(ds));
        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 ); // 此处用i+1而非ind+1
           ds.remove( ds.size() - 1 );
        }
     }   
  }
  
  private boolean ispalindrome(String s, int left, int right) {
      while(left < right) {
          if(s.charAt(left) != s.charAt(right)) return false;
          left++;
          right--;
      }
      return true;
  }
}

这里的ind代表当前待分割的起始位置：

1. 循环中i从ind开始扩展，当[ind, i]是回文时，我们把这个子串加入分割结果ds。
2. 递归调用partition(i+1, ...)是因为：我们已经处理完了从ind到i的部分，接下来需要从i+1的位置开始新的分割——剩余的待处理区间是[i+1, s.length()-1]，而不是ind+1（如果用ind+1，会重复处理ind+1到i的区间，导致分割结果重复或遗漏长回文子串的情况）。

总结 #

• 排列问题：ind是待填充的位置，递归只需推进到下一个固定位置，因此用ind+1。
• 回文分割/子集问题：ind是已处理部分的边界，递归需要推进到当前选中区间的下一个起点，因此用i+1。

内容的提问来源于stack exchange，提问作者Anchal Dobriyal