# Non-Recursive JAVA solution

• ``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
int i=0, size = candidates.length, sum=0;
Stack<Integer> combi = new Stack<>(), indices = new Stack<>();
List<List<Integer>> result = new ArrayList<>();
while (i < size) {
if (sum + candidates[i]>= target) {
if (sum + candidates[i] == target) {
combi.push(candidates[i]);
combi.pop();
}
// indices stack and combination stack should have the same size all the time
if (!indices.empty()){
sum -= combi.pop();
i = indices.pop();
while (i == size-1 && !indices.empty()) {
i = indices.pop();
sum -= combi.pop();

}
}
i++;
} else {
combi.push(candidates[i]);
sum +=candidates[i];
indices.push(i);
}
}
return result;
}``````

• Thank you to provide such precisely cogged codes which run like a boutique clock.
And it is really based on backtracking.
The only pity is the lack of comments to polish those brilliant idea.

• This is a very subtle and concise method,thank you for providing. Could you please apply it into combination sum II, I have tried but I can't, there are a lot of corner cases I can't handle.

• @qlan2

``````class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort(reverse=True)
i, s, size = 0, 0, len(candidates)
indexList, tmpResult, result = [], [], []
while i < size:
tmpResult.append(candidates[i])
indexList.append(i)
s += candidates[i]
i += 1
if s >= target or i == size:
if s == target:
result.append(tmpResult[:])

s -= tmpResult.pop()
i = indexList.pop()+1
while i == size and tmpResult:
s -= tmpResult.pop()
i = indexList.pop() + 1

return result
``````

• @sunnysuhappy
sorry this is the right one:

``````class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort(reverse=True)
i, s, size = 0, 0, len(candidates)
indexList, tmpResult, result = [], [], []
while i < size:
tmpResult.append(candidates[i])
indexList.append(i)
s += candidates[i]
i += 1
if s >= target or i == size:
if s == target:
result.append(tmpResult[:])

tmpI = tmpResult.pop()
s -= tmpI
i = indexList.pop()+1

while i >= size or tmpI == candidates[i]:
if i < size:
i += 1
else:
if tmpResult:
tmpI = tmpResult.pop()
s -= tmpI
i = indexList.pop() + 1
else:
break

return result
``````

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