Leetcode回溯

回溯问题的模版在78.子集里面展现的淋漓尽致：

答案视角：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void dfs(int i) {
      // 将当前路径（即当前构建的子集）复制并添加到结果列表中
       ans.add(new ArrayList<>(path));
      // 如果索引i等于数组长度，说明已经考虑完所有元素，返回结束递归
       if (i == nums.length) return;  
      // 从索引i开始，枚举可能选择的元素
       for (int j = i; j < nums.length; ++j) { 
      // 选择元素nums[j]，加入到当前路径中
           path.add(nums[j]);                  
      // 递归调用dfs，考虑下一个元素
           dfs(j + 1);                        
      // 撤销选择，即从path中移除最后一个元素，恢复到选择前的状态
           path.remove(path.size() - 1);       
       }
   }

选择视角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void dfs(int i) {
        // 如果索引i等于数组长度，说明已遍历完所有元素
       if (i == nums.length) {
           // 将当前路径（子集）复制并添加到答案列表中
           ans.add(new ArrayList<>(path));     
           return;
       }
       // 不选择当前元素 nums[i]
       dfs(i + 1);
       // 选择当前元素 nums[i]
       path.add(nums[i]);   // 将当前元素添加到路径中
       dfs(i + 1);          // 继续递归下一个元素
       path.remove(path.size() - 1);  // 回溯，移除路径中最后一个元素，恢复到选择前的状态
   }

在多数情况下，是答案视角符合的问题更多一些

在排列问题中，比如46.全排列和47.全排列2中，需要添加一个辅助数组onpath来标记一下某些数字是否被选

通过如下代码可以避免重复问题：

1
2
3
4
while (j < nums.length - 1 && nums[j] == nums[j + 1]&&onPath[j]==false) 
{
               ++j;
}