Question: http://oj.leetcode.com/problems/combination-sum/
Question Name: Combination Sum
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 | class Solution: # @param candidates, a list of integers # @param target, integer # @return a list of lists of integers def combinationSum(self, candidates, target): ''' Convert this question into n-sum question, by adding 0s ''' result = [] # 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 # (limit - M) 0s. candidates.append(0) candidates.sort() # The maximum number of items in one answer set limit = target // candidates[1] if limit == 0: return [] if limit == 1: if target in candidates: return [[target]] else: return [] # The pointers used for n-sum. The time complexity is O(M^(n-1)) pointers = [0] * limit pointers[-1] = len(candidates) - 1 while pointers[0] < len(candidates): 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: 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 the next round n-sum trying pointerIndex = limit - 3 while pointerIndex >= 0: pointers[pointerIndex] += 1 while pointers[pointerIndex] < len(candidates) and candidates[pointers[pointerIndex]] == candidates[pointers[pointerIndex]-1]: pointers[pointerIndex] += 1 if pointers[pointerIndex] == len(candidates): pointerIndex -= 1 else: break else: break for i in xrange(pointerIndex+1, limit-1): pointers[i] = pointers[pointerIndex] pointers[-1] = len(candidates) - 1 return result |
One Reply to “Solution to Combination Sum by LeetCode”