import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

* 39. Combination Sum

* Given a set of candidate numbers (C) (without duplicates) and a target number (T),

* find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited 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 target 7,

A solution set is:

[

[7],

[2, 2, 3]

]

time : O(2^n)

space : O(n)

* @param candidates

* @param target

* @return

*/

public class CombinationSum {

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

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

if (candidates == null || candidates.length == 0) return res;

helper(res, new ArrayList<>(), candidates, target, 0);

return res;

}

public void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) {

if (target == 0) {

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

return;

}

if(target<0)return;

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

list.add(candidates[i]);

helper(res, list, candidates, target - candidates[i], i);

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

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int nums[]= {9,2,3,6,7};

CombinationSum one=new CombinationSum();

one.combinationSum(nums,7);

}

}