39 Combination Sum

https://leetcode.com/problems/combination-sum/#/description

Given asetof candidate numbers (C)(without duplicates)and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.

Thesamerepeated number may be chosen fromCunlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set[2, 3, 6, 7]and target7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

分析及代码

很熟悉的题目……没啥要说的

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    if(candidates.length == 0) {
        return res;
    }
    generator(res, new ArrayList<>(), candidates, target, 0);
    return res;
}

private void generator(List<List<Integer>> res, List<Integer> item, int[] candidates, int remain, int index) {
    if(remain < 0) {
        return;
    }
    if(remain == 0) {
        res.add(new ArrayList<>(item));
        return;
    }
    for(int i = index; i < candidates.length; i++) {
        item.add(candidates[i]);
        generator(res, item, candidates, remain - candidates[i], i);
        item.remove(item.size() - 1);
    }
}

每一个数有两种选择，选它，不选它，所以是O(2^n)