39. 组合总和

问题39 组合总和 ★★☆☆☆

https://leetcode-cn.com/problems/combination-sum/

这个题目和问题40很像，区别在于两点： （1）问题39的入参数组无重复元素，问题40的入参数组可以包含重复元素； （2）问题39中每个元素可以使用任意次，问题40中每个元素最多只能使用1次； 稍微思考一下，就能体会出为什么有这样的设定。因为问题39中每个元素可以使用任意次，所以即便是允许入参数组包含重复元素，那么也得先排序并过滤掉重复元素，题目里限定无重复元素等于是do you a favor. 问题40允许有重复元素但每个元素至多使用1次，其实就可以理解为问题39的变种，即可以理解为在问题39的基础上限定了每个元素最多使用几次。

需要注意的点是，如何保证结果集中无重复解呢？问题39是通过控制回溯过程来保证无重复解，而问题40是通过计数频次并控制每次回溯时同一个元素使用个数来保证无重复解。注意，对于问题40，如果仅仅是排序元素，然后按照类似问题39的思路去处理，即对每个当前遍历到的元素按不使用、使用分别继续下一回合遍历，这样是不行的，因为这样处理不能保证无重复解，比如，对于数组[1,2,2,2,2]，target=5，那么你会得到多个[1,2,2]的重复解。

另外，问题39和问题40这两个combination sum，和问题1、问题167、问题15、问题16、问题18这几个sum类问题是有一定相关性的。问题39和问题40可以看作问题1、问题167、问题15、问题16、问题18这几个sum类问题的进一步推广，即不限制相加之和等于目标值的子数组的元素个数。虽然从解法上有明显区别，但是这种区别也正是问题本身的扩展化和一般化带来的。

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> combination = new ArrayList<>();

    candidates = Arrays.stream(candidates).sorted().toArray();
    backtrack(result, combination, candidates, 0,  target);

    return result;
  }

  private void backtrack(List<List<Integer>> result,
                         List<Integer> combination,
                         int[] candidates,
                         int curIdx,
                         int target) {

    if (curIdx == candidates.length) {
      return;
    }

    if (target == 0) {
      result.add(new ArrayList<>(combination)); // pay attention here
      return;
    }

    int curVal = candidates[curIdx];
    if (curVal > target) {
      return;
    }

    // curIdx excluded
    backtrack(result, combination, candidates, curIdx+1, target);

    // curIdx included
    combination.add(curVal);
    backtrack(result, combination, candidates, curIdx, target-curVal);
    combination.remove(combination.size()-1);
  }

在 LeetCode 查看