Question: http://oj.leetcode.com/problems/combination-sum-ii/
Question Name: Combination Sum II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | class Solution: # @param candidates, a list of integers # @param target, integer # @return a list of lists of integers def combinationSum2(self, candidates, target): ''' Convert this question into n-sum question, by adding 0s ''' result = [] # Rule out the integers greater than target candidates = [i for i in candidates if i <= target] if len(candidates) == 0: return [] # The maximum number of items in one answer set candidates.sort() limit = target // candidates[0] # Adjust the limit. The maximum number of items in one # answer set must be equal to or less than the number # of items in candidates if limit > len(candidates): limit = len(candidates) if limit == 0: return [] elif limit == 1: if target in candidates: return [[target]] else: return [] else: # We add a 0 at the head of candidates. If the length of # of original answer is M, the answer here will be length # of "limit", with original answer M and additional heading # (limit - M) 0s. candidates= [0] * (limit - 1) + candidates # The pointers used for n-sum. The time complexity is O(M^(n-1)) pointers = range(limit) pointers[-1] = len(candidates) - 1 while pointers[0] < len(candidates) - (limit - 1): # The innermost loop of n-sum solution preSum = sum([candidates[i] for i in pointers[:-2]]) if preSum + candidates[pointers[-2]] + candidates[pointers[-2]] > target: # All combinations in this round are too big pass elif preSum + candidates[pointers[-1]] + candidates[pointers[-1]] < target: # All combinations in this round are too small pass else: # These two pointers cannot point to one same cell, because each cell # can be used once at most. while pointers[-2] < pointers[-1]: temp = preSum + candidates[pointers[-2]] + candidates[pointers[-1]] moveAhead, moveBack = False, False if temp > target: moveBack = True elif temp < target: moveAhead = True else: # Found a qualified combination result.append([candidates[i] for i in pointers if candidates[i] != 0]) moveAhead, moveBack = True, True if moveBack: pointers[-1] -= 1 while pointers[-2] <= pointers[-1] and candidates[pointers[-1]] == candidates[pointers[-1]+1]: pointers[-1] -= 1 if moveAhead: pointers[-2] += 1 while pointers[-2] <= pointers[-1] and candidates[pointers[-2]] == candidates[pointers[-2]-1]: pointers[-2] += 1 # Adjust the pointers for next round n-sum trying pointerIndex = limit - 3 while pointerIndex >= 0: pointers[pointerIndex] += 1 while pointers[pointerIndex] < len(candidates) - (limit - (pointerIndex + 1)) and candidates[pointers[pointerIndex]] == candidates[pointers[pointerIndex]-1]: pointers[pointerIndex] += 1 if pointers[pointerIndex] == len(candidates) - (limit - (pointerIndex + 1)): pointerIndex -= 1 else: break else: break for i in xrange(pointerIndex+1, limit-1): pointers[i] = pointers[i-1] + 1 pointers[-1] = len(candidates) - 1 return result |