39 combination sum

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

注意这里吐不是立马吐，是add完之后再吐，同时注意用.subList(presize, size).clear()的神奇吐法

class Solution {
     List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, 0, new ArrayList<>(), target, 0);
        return ans;
    }
    private void dfs(int[] candidates, int index, List<Integer> path, int target, int sum) {
        if (sum > target) return;
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (index == candidates.length) {
            return;
        }
        dfs(candidates, index + 1, path, target, sum);
        int presize = path.size();
        while (sum < target) {
            sum += candidates[index];
            path.add(candidates[index]);
            dfs(candidates, index + 1, path, target, sum);
        }
        path.subList(presize, path.size()).clear();
    }
}