那种输出全部组合的List＜List＜Integer＞＞题

这种因为是要输出全部可能的组合而不是组合的数量，所以一定要恢复现场 也就是回溯法

最常见类型有 组合总和 1 2 3 4

套路有

1.  常见模板1 

 for(int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i-1]) continue;
            list.add(candidates[i]);
            helper(candidates, target, i+1, rest-candidates[i]);
            list.remove(list.size()-1);
        }

常见模板 2 （每个数可以重复拿 零钱取整题  组合总和4） 

顺序不同的序列被视作不同的组合。

 for(int num : nums) {
            
            list.add(num);
            helper(nums, target, i+1, rest-num);
            list.remove(list.size()-1);
        }

常见模板3  （全排列题做法）

 for(int i = 0; i < candidates.length; i++) {
            
            list.add(candidates[i]);
            helper(candidates, target, i+1, rest-candidates[i]);
            list.remove(list.size()-1);
        }

常见模板4 全排列题外加

全排列题除了list的回溯与保存

还有下标的回溯与保存 因为1 2 3的全排列 你如果不排除下标有没有用过 会有1 1 1  ，1 2 1的情况

所以要用Set集合 或者！！！！ 一个boolean[ ] used数组来保存下标是否使用过

去重方法！！！ 去重的前提是先进行排序！！！

2. Arrays.sort(candidates); 对给的数组先进行升序排列，可以去除如果有多个重复数字 重复拿的情况 如组合总和 2 

比如 1 3 1 5 6 2 2 3 这种 不先进行排序的话就会导致 刚才拿了1 后面可能又会拿个1

 

3.  除了排序外 为防止重复拿 可以加上这一句

if(i > index && candidates[i] == candidates[i-1]) continue;

全排列的防止重复拿：只要前一个没用过 那肯定不再需要了 一定会重复

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

if(i > 0 && nums[i] == nums[i-1] && set.contains(i-1)== false) {continue;}

4.  用 一个boolean[ ] used数组来保存下标是否使用过

5. 想要去重就用Set