We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Combination Sum

Difficulty: Medium

Problem 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.

Key Insights

  • The problem requires finding combinations that sum to a target, allowing repeated use of the same elements.
  • Backtracking is an effective approach to explore all possible combinations recursively.
  • The input constraints ensure the number of unique combinations is manageable, simplifying the implementation.

Space and Time Complexity

Time Complexity: O(2^(target/min(candidates))) - The worst-case scenario occurs when all candidates can potentially be part of the combinations leading to the target.

Space Complexity: O(target) - The space complexity is mainly due to the recursion stack depth.

Solution

The problem can be solved using a backtracking algorithm. The approach involves:

  1. Starting from an empty combination, recursively add candidates to the current combination.
  2. If the sum of the current combination equals the target, save the combination.
  3. If the sum exceeds the target, backtrack and try the next candidate.
  4. Repeat until all candidates are considered.

The algorithm employs a list to store the current combination and another list to collect all valid combinations.

Code Solutions

def combinationSum(candidates, target):
    res = []
    
    def backtrack(remaining, combo, start):
        if remaining == 0:
            res.append(list(combo))
            return
        elif remaining < 0:
            return
        
        for i in range(start, len(candidates)):
            combo.append(candidates[i])
            backtrack(remaining - candidates[i], combo, i)  # not i + 1 because we can reuse the same elements
            combo.pop()  # backtrack
    
    backtrack(target, [], 0)
    return res
← Back to All Questions