LeetCode之组合总数

**题目：**给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。
  示例：
  
  提示：
  
  方法一：动态规划
  

// 由@liu-li-8提供
class Solution {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> result = new ArrayList<>();
      Map<Integer,Set<List<Integer>>> map = new HashMap<>();
      //对candidates数组进行排序
      Arrays.sort(candidates);
      int len = candidates.length;
      for(int i = 1;i <= target;i++){
          //初始化map
          map.put(i,new HashSet<>());
          //对candidates数组进行循环
          for(int j = 0;j < len&&candidates[j] <= target;j++){
              if(i == candidates[j]){
                  //相等即为相减为0的情况，直接加入set集合即可
                  List<Integer> temp = new ArrayList<>();
                  temp.add(i);
                  map.get(i).add(temp);
              }else if(i > candidates[j]){
                  //i-candidates[j]是map的key
                  int key = i-candidates[j];
                  //使用迭代器对对应key的set集合进行遍历
                  //如果candidates数组不包含这个key值，对应的set集合会为空，故这里不需要做单独判断
                  for(Iterator iterator = map.get(key).iterator();iterator.hasNext();){
                      List list = (List) iterator.next();
                      //set集合里面的每一个list都要加入candidates[j]，然后放入到以i为key的集合中
                      List tempList = new ArrayList<>();
                      tempList.addAll(list);
                      tempList.add(candidates[j]);
                      //排序是为了通过set集合去重
                      Collections.sort(tempList);
                      map.get(i).add(tempList);
                  }
              }
          }
      }
      result.addAll(map.get(target));
      return result;
  }
}

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dict = {}
        for i in range(1,target+1):
            dict[i]=[]
        
        for i in range(1,target+1):
            for j in candidates:
                if i==j:
                    dict[i].append([i])
                elif i>j:
                    for k in dict[i-j]:
                        x = k[:]
                        x.append(j)
                        x.sort() # 升序，便于后续去重
                        if x not in dict[i]:
                            dict[i].append(x)

        return dict[target]

方法二：搜索回溯

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}