题目

image.png

思路

  • 思路一：dfs+回溯，遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。具体的做法是：每一次搜索的时候设置 下一轮搜索的起点 index
  • 思路二：dfs+回溯+剪枝

  • 思路三：其实这个问题类似于零钱兑换 II问题，因此可以转换为完全背包问题，但是用来找组合不方便，还是dfs+回溯比较方便

    代码

    1.   //错误写法
    2.   public List<List<Integer>> combinationSum(int[] candidates, int target) {
    3.       List<List<Integer>> res = new ArrayList<>();
    4.       dfs(candidates, target, 0, res, new ArrayList<>());
    5.       return res;
    6.   }
    8.   public void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> tmp) {
    9.       if (0 == target) res.add(new ArrayList<>(tmp));
    10.       if (target <= 0) return;
    11.       for (int i = index; i < candidates.length; i++) {
    12.           tmp.add(candidates[i]);
    13.           //失败写法在index，不更新会导致重复结果，用不同起点确保了不会重复
    14.           dfs(candidates, target - candidates[i], index, res, tmp);
    15.           tmp.remove(tmp.size() - 1);
    16.       }
    17.   }
    19.   //1.dfs+回溯
    20.   public List<List<Integer>> combinationSum(int[] candidates, int target) {
    21.       List<List<Integer>> res = new ArrayList<>();
    22.       dfs(candidates, target, 0, res, new ArrayList<>());
    23.       return res;
    24.   }
    26.   public void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> tmp) {
    27.       if (0 == target) res.add(new ArrayList<>(tmp));
    28.       if (target <= 0) return;
    29.       for (int i = index; i < candidates.length; i++) {
    30.           tmp.add(candidates[i]);
    31.           dfs(candidates, target - candidates[i], i, res, tmp);
    32.           tmp.remove(tmp.size() - 1);
    33.       }
    34.   }
    36.   //2.dfs+回溯+剪枝
    37.   public List<List<Integer>> combinationSum(int[] candidates, int target) {
    38.       List<List<Integer>> res = new ArrayList<>();
    39.       //排序方便剪枝
    40.       Arrays.sort(candidates);
    41.       dfs(candidates, target, 0, res, new ArrayList<>());
    42.       return res;
    43.   }
    45.   public void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> tmp) {
    46.       if (0 == target) res.add(new ArrayList<>(tmp));
    47.       if (target <= 0) return;
    48.       for (int i = index; i < candidates.length; i++) {
    49.           //小于时就剪枝
    50.           if (target < candidates[i]) return;
    51.           tmp.add(candidates[i]);
    52.           dfs(candidates, target - candidates[i], i, res, tmp);
    53.           tmp.remove(tmp.size() - 1);
    54.       }
    55.   }

    组合总和