# A solution avoid using set

• Sort the candidates and we choose from small to large recursively, every time we add a candidate to our possible sub result, we subtract the target to a new smaller one.

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // sort the candidates
// collect possible candidates from small to large to eliminate duplicates,
recurse(new ArrayList<Integer>(), target, candidates, 0, ret);
return ret;
}

// the index here means we are allowed to choose candidates from that index
private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) {
if (target == 0) {
return;
}
for (int i = index; i < candidates.length; i++) {
int newTarget = target - candidates[i];
if (newTarget >= 0) {
List<Integer> copy = new ArrayList<Integer>(list);
recurse(copy, newTarget, candidates, i, ret);
} else {
break;
}
}
}``````

• Slightly modified your solution, this will make the method run a little faster.

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // sort the candidates
// collect possible candidates from small to large to eliminate duplicates,
recurse(new ArrayList<Integer>(), target, candidates, 0, ret);
return ret;
}

// the index here means we are allowed to choose candidates from that index
private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) {
if (target == 0) {
return;
}
for (int i = index; i < candidates.length; i++) {
int newTarget = target - candidates[i];
if (newTarget >= 0) {
List<Integer> copy = new ArrayList<Integer>(list);
recurse(copy, newTarget, candidates, i, ret);
}else{
break;
}
}``````

• That's a good break

• I don't get why you guys need the for loop, totally unnecessary.

``````class Solution {
public:
vector<vector<int> > result;
vector<int> output;

vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
sort(candidates.rbegin(), candidates.rend());
search(candidates.begin(), candidates.end(), target);
return result;
}

void search(vector<int>::iterator begin, vector<int>::iterator end, int target) {
if (target == 0) {
result.push_back(output);
sort(result.back().begin(), result.back().end());
return;
}

if (begin == end)
return;

if (*begin <= target) {
output.push_back(*begin);
search(begin, end, target-*begin);
output.pop_back();
}

search(begin+1, end, target);
}
};``````

• what is the time and space complexity of this solution? Seems like it would be:

Time: O(n*m), where n is size of candidate set, and m == target. Consider target = 1 million, and set = (1,2,3). On the first iteration, we would recurse a million times to form the set (1,1,1,1....). 2 would be 500,000 recursions.

Space: O(m) due to stack frames

• This post is deleted!

• Regarding your code, what if you meet candidates = [1,1], target = 1. It's gonna output [[1],[1]]. And also, the time complexity is O(n!) scale

Yeah, you're correct! Even though this case happens, it is easily checked using a HashSet.

• For this problem, I think the assumption is there's no duplicate in candidates.

• Hi what's your former code without using the "break".

I came out with a similar way with yours. But I didn't realize the else {} should use break

Thanks

• Just delete the else clause is my former code.

• the code above cannot generate unique answers when the candidates contain same numbers. ex: [2, 2, 3, 6, 7], target = 7. it will generate [2, 2, 3] three times.

• the code above cannot generate unique answers when the candidates contain same numbers. ex: [2, 2, 3, 6, 7], target = 7. it will generate [2, 2, 3] three times.

my code here will skip the number that are same as the next number.

public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(candidates.length <= 0)
return res;
Arrays.sort(candidates);
ArrayList<Integer> line = new ArrayList<Integer>();
finder(res, line, target, candidates, 0);
return res;
}
public void finder(List<List<Integer>> res, ArrayList<Integer> line, int target, int[] candidates, int i)
{
if(target == 0)
{
return;
}
if(i >= candidates.length)
return;
if(target < 0)
return;
for(int j = i; j < candidates.length; j++)
{
//skip the same integers
while(j+1 < candidates.length && candidates[j+1] == candidates[j])
{
j++;
}
if(target-candidates[j] >= 0)
{
ArrayList<Integer> tmp = new ArrayList<Integer>();
finder(res, tmp, target-candidates[j],candidates,j);
}
}
}

• Nice, but why reverse the candidates then reverse the output back again?

• I think newTarget should >= candidates[i], not 0. In that case, we can reduce some cases.
What's more, I think there may be some memory leaks. i.e. [1,2,3,4],target 6, when you test [2, 3 ....], you will copy array [2, 3], but you will not free it .

• To keep the results in non-descending order

• i think the question implies that there will be no duplicates in the candidates, since it says the candidates is a set.

• Yes, that makes a lot of sense

• Would this not generate multiple copies of [1,1] for inputs like [1,1,1,1] and target = 2 ?

• You are right. The assumption of this answer is candidates[] has all unique numbers.

To avoid duplicate in your example, you can add below line in the beginning of the loop :) if(i>index&&candidates[i]==candidates[i-1]) continue;

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.