[LeetCode] 039. Combination Sum *

• Problem (Medium)
• Approach 1: Depth First Search (Backtracking)
  • Idea
  • Solution
  • Complexity

Problem (Medium)

039. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ]

Example 2:

Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]

Approach 1: Depth First Search (Backtracking)

Idea

• A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)
• What is Depth First Search?

Solution

class Solution1:
    def combinationSum(self, candidates, target):
        """ 
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(candidates, target, 0, [], res)
        return set([tuple(i) for i in res])

    def dfs(self, nums, target, index, path, res):
        if target < 0:
            return # backtracking
        if target == 0:
            res.append(path)
            return
        for i in range(index, len(nums)):
            self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

Complexity

• Time: $O()$?
• Space: $O()$?

KF