题目

分析

回溯问题最简单的思想就是直接dfs暴力搜索，找出每一种情况即可，不过这样的时间效率不会很高，需要进一步的优化(剪枝)。另外，题目需要得到和为 target 的组合的集合，由于给定数组没有重复元素，故只要保证 下一次搜索的数的下标 >= 当前下标 即可避免出现重复解集。我们可以采用减法使得每次遍历到一个数就将 target 值减去遍历元素传递给更深一层，target <= 0 时递归结束返回(当然加法也同理，用一个变量记录和，和等于 target 时递归结束返回)。分析图如下：

可以得到代码如下：

class Solution {

    List<List<Integer>> ans = new ArrayList();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, new Stack<Integer>());
        return ans;
    }

    public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(com));
        } else if (target > 0) {
            for (int i = index; i < candidates.length; i++) {
                com.push(candidates[i]);
                dfs(candidates, target - candidates[i], i, com);
                com.pop();
            }
        }
    }
}

成功AC，不过时间方面还可以再优化。

优化

通过观察分析图，可以发现，对于排好序的数组，只要小的数不满足条件，后边的元素遍都可以不用遍历了，从而可以实现剪枝，代码如下：

class Solution {

    List<List<Integer>> ans = new ArrayList();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //排序方便剪枝
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new Stack<Integer>());
        return ans;
    }

    public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(com));
        } else if (target > 0) {
            for (int i = index; i < candidates.length; i++) {
                //数组元素比当前目标大，后边的元素都不用遍历了
                    if (target < candidates[i])
                    break;
                com.push(candidates[i]);
                dfs(candidates, target - candidates[i], i, com);
                com.pop();
            }
        }
    }
}

提交后大概3ms，比较令人满意的效率。

组合总和Ⅱ

题目如下：

分析

与第一题相比，数组包含重复元素，但是每个数字只能使用一次，这就说明，在第一题基础上，当向深层遍历的时候只能从当前的元素向后遍历(不含当前元素)。但是有重复元素，哪怕排完序也会出现重复的解集组合，不过对于下面数组示例可以发现：

排序后的数组对于重复的数字会出现重复的解，但是第一个元素(第一个1、3)不会出现重复，所以，从第一个之后跳过所有重复的数字即可，即：

/* 跳过重复的数字 */
if (i > index && candidates[i] == candidates[i - 1])
                    continue;

完整代码

class Solution {

    ArrayList<List<Integer>> ans = new ArrayList();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, new Stack<Integer>(), 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, Stack<Integer> stack, int index) {
        if (target < 0) {
            return;
        } else if (target == 0) {
            ans.add(new ArrayList<Integer>(stack));
        } else {
            for (int i = index; i < candidates.length; i++) {
                if (candidates[i] > target) {
                    break;
                }

                if (i > index && candidates[i] == candidates[i - 1])
                    continue;
                stack.add(candidates[i]);
                dfs(candidates, target - candidates[i], stack, i + 1);
                stack.pop();
            }
        }
    }
}

整体思路与第一题没什么差别，主要是一点细节上的处理。

组合总和Ⅲ

题目如下：

第三题思路与前两题基本一致，甚至难度比前两题还要小一点，就不再讲解，给出完整代码：

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
         ArrayList<List<Integer>> ans = new ArrayList();
         dfs(k, n, ans, new Stack<Integer>(), 1);
         return ans;
    }

    public void dfs(int k, int n, ArrayList<List<Integer>> ans, Stack<Integer> stack, int start){
        if(k == 0){
            if(n == 0){
                ans.add(new ArrayList(stack));
            }
        }else{
            for(int i = start; i <= 9; i++){
                stack.push(i);
                if(i > n){
                    stack.pop();
                    break;
                }
                   
                dfs(k - 1, n - i, ans, stack, i + 1);
                stack.pop();
            }
        }
    }
}

认真总结，仔细研究，未来可期。