Combination Sum

Description

https://leetcode.com/problems/combination-sum/description/

Solution

BFS

The naive implementation of BFS, in this algorithm, we need a lot of space to record the state, and the time spent on copying these states is tremendous.

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(candidates) == 0:
            return []
        
        new_candidates = sorted(candidates)
        ret = []
        result_stack = []
        candidate_lens = len(new_candidates)
        for index in range( 0, candidate_lens ):
            new_candidate = new_candidates[index]
            if new_candidate == target:
                ret.append([new_candidate])
            else:
                result_stack.append([ [new_candidate], index, new_candidate] )
                
        while(result_stack != []):
            new_result_stack = []
            for index in range(0, len(result_stack)):
                current_sum = result_stack[index][2]
                next_index = result_stack[index][1]
                
                ##The result stack is full
                if next_index >= candidate_lens:
                    continue    
                for inner_index in range(next_index, candidate_lens):
                    candidate = new_candidates[inner_index]
                    if current_sum + candidate < target:
                        s = result_stack[index][0][:] ##COPY
                        s.append(candidate)
                        new_item = [s, inner_index, candidate + current_sum]
                        new_result_stack.append(new_item)
                     
                    if current_sum + candidate == target:
                        s = result_stack[index][0][:]
                        s.append(candidate)
                        ret.append(s)
                        break
            result_stack = new_result_stack
        
        return ret

DFS

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        new_candidates = sorted(candidates)
        ret = []
        self.get_result(ret, new_candidates, [], target, 0)
        return ret
        
    def get_result(self, ret, candidates, candidates_list, remain, index):
        
        if remain < 0:
            return
        if remain == 0:
            ret.append(candidates_list[:])
            return
        
        traverse_index = index
        while(traverse_index < len(candidates) and candidates[traverse_index] <= remain):
            candidates_list.append(candidates[traverse_index])
            self.get_result(ret, candidates, candidates_list, remain - candidates[traverse_index], traverse_index)
            candidates_list.pop()            
            traverse_index += 1
      
        return

Non_Recursive Solution(DFS)

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        ret = []
        lens = len(candidates)
        remain = target
        stack = [[-1, target]]
        path = []
        current_index = 0
        while stack:
            item = stack[-1]
            current_index = item[0] + 1
            stack[-1][0] = current_index
            if current_index >= lens:
                if stack:
                    stack.pop()
                if path:
                    path.pop()
                continue
            remain = item[1]
            while remain >= candidates[current_index]:
                remain -= candidates[current_index]
                stack.append( [current_index, remain] )
                path.append(candidates[current_index])
                
            if remain == 0:
                ret.append(path[:])
                path.pop()
                stack.pop()
            if path:
                path.pop()
            if stack:
                stack.pop()
            
            print (path)
            print(stack)
            print()
        return ret

But the result is upsetting, the recursive method performs better than the non-recursive solution.