自己解法

因为有每步减做拆解的感觉，就想到了深度优先遍历加回溯，这也是我理解最深的递归了吧哈哈，并且这种数组为了剪枝一般都是先排序，不过这个题我忽略了，只排了序，没去重，

后面补上了下标只能越去越大就好了。

class Solution {

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        Arrays.sort(candidates);

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

        dfs(candidates, target, res, 0);

        return output;

    }

    private void dfs(int[] candidates, int target, List<Integer> res, int j) {

        if (target == 0) {

            output.add(new ArrayList(res));

        }

        for (int i = j; i < candidates.length; i++) {

            if (candidates[i] > target) {

                break;

            }

            res.add(candidates[i]);

            dfs(candidates, target - candidates[i], res, i);

            res.remove(res.size() - 1);

        } 

    }

}

官方解法

解法完全一样，就是他这个有点啰嗦，还有剪枝的时候可以直接break，以为后面越取越大了。

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Deque;

import java.util.List;

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

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

        int len = candidates.length;

        // 排序是为了提前终止搜索

        Arrays.sort(candidates);

        dfs(candidates, len, target, 0, new ArrayDeque<>(), res);

        return res;

    }

    /**

    * @param candidates 数组输入

    * @param len        输入数组的长度，冗余变量

    * @param residue    剩余数值

    * @param begin      本轮搜索的起点下标

    * @param path      从根结点到任意结点的路径

    * @param res        结果集变量

    */

    private void dfs(int[] candidates,

                    int len,

                    int residue,

                    int begin,

                    Deque<Integer> path,

                    List<List<Integer>> res) {

        if (residue == 0) {

            // 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝

            res.add(new ArrayList<>(path));

            return;

        }

        for (int i = begin; i < len; i++) {

            // 在数组有序的前提下，剪枝

            if (residue - candidates[i] < 0) {

                break;

            }

            path.addLast(candidates[i]);

            dfs(candidates, len, residue - candidates[i], i, path, res);

            path.removeLast();

        }

    }

}