解析思路

leetcode 中等难度,题目描述点击这里

标准的回溯类题目,对于回溯类题目,通常都是要穷举所有的情况,然后判断那些情况是符合题目要求的。

然后穷举通常是通过深度优先搜索(dfs)来实现的,我们可以先将结果展开成一棵树,然后再根据这棵树来写代码,就比较好理解,如下图:

以[2,3,5],8 为例:

展开

上图只对最左边的路径进行了完全展开(全部展开太麻烦了)

总的来说回溯就是不断的进行尝试,如果尝试到最后发现不满足要求那就换一个路径继续尝试,属于暴力算法。因此此类题目的数据规模通常会限制的比较小。

另外通常还能根据题目的要求来做剪枝操作,减少一些不必要的运算。

比如本题可以先将数组排序,当选择的某个数已经大于目标值时,就没必须选择这个数的下一个数继续尝试了。

代码

public class Q39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
		//排序
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new Stack<>(), res);
        return res;
    }

    private void dfs(int[] candidates, int target, int index, Stack<Integer> temp, List<List<Integer>> res) {
        if (target == 0) {
            //说明找到一个结果序列
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] > target) {
                //前面已经排序过,所以在这里可以进行剪枝操作,如果candidates[index]都小于target了,那就不需要比较后面的了,肯定不满足要求
                return;
            }
            temp.push(candidates[i]);
			//注意这里,为了让结果集不重复,选择重复元素时只能对当前元素进行重复选择,不能重复选择之前的元素。所以递归的index为i,不是0
            dfs(candidates, target - candidates[i], i, temp, res);
            temp.pop();
        }
    }

    public static void main(String[] args) {
        new Q39().combinationSum(new int[]{2, 3, 5}, 8).forEach(System.out::println);
    }
}