39.组合总数

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

：做题思考全过程

思路难点：想到传入这个idx参数，否则会出现res结果中出现重复的（顺序不同）list结果。

class Solution {      List<List<Integer>> res = new ArrayList<>();      List<Integer> temp = new ArrayList<>();      public List<List<Integer>> combinationSum(int[] candidates, int target) {         backtrace(candidates, target, 0);         return res;     }      // 将传入数组和当前需要的sum？     // idx记录上一个递归增加的元素的下标，让本次遍历增加元素从这个下标开始     public void backtrace(int[] candidates, int target, int idx){         // 不能写一起，不让第一个条件判断不符合直接会执行下面语句，根本不会看第二个判断条件         // 顺序错了，要先判断是否target符合条件，再判断直接去重if(candidates[idx] > target) return;         // if(target < 0 || candidates[idx] > target) return;          if(target < 0) return;         if(target == 0){             // 去重？             if(!res.contains(temp)) res.add(new ArrayList(temp));             return;         }         // candidates数组是递增的？         // 不是递增的。不适合用下面语句剪枝优化         // if(candidates[idx] > target) return;         // 也可以先对candidates数组排序，再使用这个优化          // for遍历candidates         // 为了达到去重目的，不让i从0开始遍历。改为         for(int i = idx; i < candidates.length; i++){             temp.add(candidates[i]);             backtrace(candidates, target - candidates[i], i);             temp.remove(temp.size()-1);         }     }  }

：默写一遍，加深印象

List<List<Integer>> res = new ArrayList<>();  List<Integer> temp = new ArrayList<>();  public List<List<Integer>> combinationSum(int[] candidates, int target){     backtrace(candidates, target, 0);     return res; }  public void backtrace(int[] candidates, int target, int idx){     if(target < 0) return;     if(target == 0) {         res.add(new ArrayList(temp));         return;     }     for(int i = idx; i < candidates.length; i++){         temp.add(candidates[i]);         backtrace(candidates, target - candidates[i], i);         temp.remove(temp.size()-1);     } }