【随想录9 】回溯及模版（子集、排列问题）

模版

// 结果集合
		public List<List<Integer>> res = new ArrayList<>();
// 路径集合
    public LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> model(int[] nums) {
      // 根据是否需要指定开始位置进行传参
        backtracking(nums,0);
        return res;
    }
    public void show(int []nums,int index){
      // 根据结果叶子节点还是节点进行结果收集
        res.add(new ArrayList<>(path));
        //根据 是否需要依赖上一位置进行遍历
        for(int i=index;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }

待选元素互不相同

数组元素互不相同，所以不需要考虑去重的问题

收集的结果应该是递归树中的每一个节点，所以在进入回溯函数之后就直接收集结果

    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return res;
    }
    public void show(int []nums,int index){
        res.add(new ArrayList<>(path));
     
        for(int i=index;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }	

待选元素可能相同

可能包含重复元素，需要进行去重处理

借助卡哥的图翻译翻译：

可以使用一个标记数组来判断待选集合中每个元素是否被使用过，

以【1，2，2】 为例子

最左边的遍历会产生【】、【1】、【1，2】、【1，2，2】 这四个集合

在【1，2，2】 产生之后会往上回溯，先回溯到集合为【1，2】，因为没有新的元素可以使用，再回溯到集合中只有【1】

此时第一个2已经使用过，而唯一可以选的元素的值也是2，需要跳过

对应下面代码中的

 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==true)
    continue;        

它的意思是，如果当前待选元素与前一个元素相等，且前一个元素已经使用过了，那么这条分支就不应该继续往下走，因为前面已经走过了，所以continue，继续当前位置的 的 下一个元素的选择。

代码：

class Solution {
   List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
   LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
   boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            result.add(path);
            return result;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }
    
    private void subsetsWithDupHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==true){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

优化：

如果当前选择的元素大于了开始选择的位置

且这个数字和它前面的数字一样，那就跳过

因为在选择这个元素之前，一定选择过了之前的和它相等的元素，（i>start）

if(i>start && nums[i-1]==nums[i])continue;

完整代码：

    List<List<Integer>>  res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
      Arrays.sort(nums);
      subsetsWithDupHelper(nums,0);
      return res;
    }

    private void subsetsWithDupHelper( int[] nums, int start ) {
      res.add( new ArrayList<>(path) );

      for ( int i = start;i<nums.length;i++ ){
        if(i>start && nums[i-1]==nums[i])continue;
        path.add( nums[i] );
        subsetsWithDupHelper( nums,i+1 );
        path.removeLast();
      }
    }
  

待选元素可能相同–且有附加要求

题目要求所有递增的子序列，且不能重复

🌰 【4，6，7（a），7（b）】 字母是为了标识相同元素

结果中可以有【4，7（a）】或 【4、7（b）】 但不能两个同时存在

借助卡哥的图分析分析：