Skip to content

39. Combination Sum

Medium

Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

Solutions πŸ”’

Video Solution Coming Soon

Approach 1: Recursive Backtracking (Pick, Skip)

Time complexity: \(O(2^n \times n)\)

Space complexity: \(O(n)\), where \(n\) is the length of the array \(candidates\).

  candidates[i]
   /      \
  pick      skip

Algorithm

  1. For every position in candidate we will either pick the element or skip the element in current list cur
  2. While picking the element recursively we can pick the same element multiple times
  3. Terminate the function on various conditions
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    n = len(candidates)

    def backtrack(cur: List[int] , i: int) -> None:
        if sum(cur) == target:
            ans.append(copy.deepcopy(cur))
            return                              #Dont Forget to return

        if i == n or sum(cur) > target:
            return

        #pick the element at position i, given we can pick the same element multiple times to reach to target
        backtrack(cur + [candidates[i]] , i) # Here when we are picking we can pick the same element multiple times to reach to target sum i.e why in function backtrack argument i is i and not i+1

        #skip the element at position i and move ahead
        backtrack(cur, i + 1)

    backtrack([], 0)
    return ans
equivalency 
copy.deepcopy(cur)  # deepcopy

# shallow copy
copy.copy(cur)
  ||
  ||
  ||
cur[::]     #slice notation
  ||
  ||
  ||
cur[:]      #slice notation
  ||
  ||
  ||
cur.clone()

Approach 2 : Recursive Backtracking (Loop)

πŸ‘‰ I prefer this

Time complexity: \(O(∣candidates∣^{target})\)

Space complexity: \(O(target)\)

Algorithm

  1. Make the recursive decision tree, then we will realize it is a backtracking
  2. Start the dfs with empty path list and the current level i.e 0

  3. The tree branches are seen through for loop , the for loop starts from the current level

    We can pick the same element multiple times from the candidate list in the path list when we are backtracking

  4. Prune the tree meaning return if the sum(path) becomes more than the target

  5. Store/Save the path if sum(path) reaches target
  6. Upon returning from a level pop out the last added elemet in the past list
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    n = len(candidates)

    def dfs(path: List[int], s: int) -> None:
        if sum(path)==target:
            ans.append(path[::])
            return

        if sum(path) > target:
            return

        for i in range(s,n):
            path.append(candidates[i])
            dfs(path,i)
            path.pop()

    dfs([],0)
    return ans
equivalency 
path.append(candidates[i])
dfs(path, i+1)
path.pop()

    ||
equivalent
    ||

dfs(path + [candidates[i]], i)

Approach 3 : Sorting + Pruning + Backtracking

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    n = len(candidates)

    def dfs(s: int, target: int, path: List[int]) -> None:
        if target < 0:
            return

        if target == 0:
            ans.append(path.clone())
            return

        for i in range(s, n):
            path.append(candidates[i])
            dfs(i, target - candidates[i], path)
            path.pop()

        candidates.sort()
        dfs(0, target, [])
    return ans
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments