# Python iterative solution

• ``````class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers

def combinationSum2(self, candidates, target):
candidates.sort()
subs = [[]]
result = []
for i in xrange(len(candidates)):
if candidates[i] > target:
break
elif candidates[i] == target:
result.append([target])
break
else:
if i > 0 and candidates[i] == candidates[i-1]:
start = last_len
else:
start = 0
last_len = len(subs)
for j in xrange(start, len(subs)):
value = sum(subs[j]) + candidates[i]
if value == target:
result.append(subs[j] + [candidates[i]])
elif value < target:
subs.append(subs[j] + [candidates[i]])

return result
``````

The above-shared solution can be further optimized. For example, if [1,2,3] + candidates[i] > target, then [1,2,3] should be removed, considering candidates[i+1] >= candidates[i], as a result, we can reduce calculation time.

But removing item from list which is not the last one wastes much time. Maybe list is a good solution. I will try it.

• I have come up with a simpler iterative version, inspired by the post "Simple and fast DFS solution, python AC 98ms" in for Combination Sum. The idea is to push the total of current combination and start index onto stack. Thus there is no need to calculate sum of current combination and the tricky handling of start index

``````class Solution:
# @param {integer[]} candidates
# @param {integer} target
# @return {integer[][]}
def combinationSum2(self, candidates, target):
candidates.sort()
combinations, stack = [], [(0, 0, [])]
while stack:
(total, start, combination) = stack.pop()
for index in range(start, len(candidates)):
sum = total + candidates[index]
if sum < target:
if (index == start) or (candidates[index] != candidates[index-1]):
# avoid duplicates
stack.append((sum, index+1, combination + [candidates[index]]))
else:
if sum == target:
combinations.append(combination + [candidates[index]])
# no need to try any more
break
return combinations
``````

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