力扣 39 组合总和

题意：给定一个数组和一个target值，返回和为target且为给定数组子数组的所有结果

思路：深度优先搜索遍历每一种可能结果，具体解析见代码注释

思想：DFS

复杂度：时间O(n²)，空间O(n^2)

class Solution {
    // 结果数组
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        // 数组为空直接返回结果
        if(len == 0)
            return res;
        build(candidates, target, 0, 0, new ArrayList<Integer>());
        return res;
    }
    // dfs
    // a是给定数组
    // target是目标和
    // index是每次递归开始的数组节点，用来去重复结果，比如[2,3,2], [2,2,3]就是重复结果
    // sum当前子数组的和
    // temp当前子数组
    void build(int[] a, int target, int index, int sum, List<Integer> temp) {
        // 当前子数组的和大于目标和返回
        if(sum > target)
            return;
        // 当前子数组的和等于目标和，加入结果并返回
        if(sum == target) {
            res.add(new ArrayList(temp));
            return;
        }
        // 对index到数组结尾的每一个元素进行dfs
        for(int i=index;i<a.length;i++) {
            temp.add(a[i]);
            build(a, target, i, sum + a[i], temp);
            temp.remove(temp.size()-1);
        }
    }
}