[39]组合总和

参考：

https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

class Solution:
    def combinationSum(self, candidates, target: int):
        results = list()
        candidates.sort()

        self.dfs(0, [], 0, results, target, candidates)
        return results

    def dfs(self, start, nums, now_all, results, target,candidates):
        if now_all == target:
            results.append(nums[:])
            return

        for i in range(start, len(candidates)):
            nums.append(candidates[i])
            now_all = sum(nums)
            if now_all > target:
                return

            self.dfs(i, nums.copy(), now_all, results, target,candidates)
            nums.pop()


if __name__ == '__main__':
    x = Solution()
    candidates = [2, 3, 6, 7]
    target = 7
    print(x.combinationSum(candidates, target))

```

package T39组合总和;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    private List<List<Integer>> results = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        dfs(candidates, target,new LinkedList<Integer>(){},0, 0);
        return results;
    }

    private void dfs(int[] candidates, int target, List<Integer> result,int start, int sum) {
        if (sum == target) {
            results.add(new LinkedList<>(result));
        }

        for (int i = start; i < candidates.length; i++) {
            if (sum > target) {
                break;
            }
            sum += candidates[i];
            result.add(candidates[i]);
            dfs(candidates, target, result, i, sum);
            sum -= candidates[i];
            result.remove(result.size() - 1);
        }

    }

    public static void main(String[] args) {
        Solution x = new Solution();
        System.out.println(x.combinationSum(new int[]{2, 3, 6, 7}, 7));

    }

}