algoadvance

Leetcode 39. Combination Sum

Problem Statement

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 input parameters are:

• candidates: an array of integers with no duplicates.
• target: an integer.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[7],[2,2,3]]

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

Clarifying Questions

1. Should the output list of combinations be sorted in any particular order?
   • No, the problem statement specifies that the combinations can be returned in any order.
2. Can the array candidates be modified?
   • No, you should not modify the input array.
3. Are negative numbers allowed in candidates?
   • In typical implementations of this problem, negative numbers are not expected because we are summing up to a positive target.
4. Is the input guaranteed to have at least one solution?
   • No, there might be cases where no combination sums up to the target, and an empty list should be returned in such cases.

Strategy

We can solve this problem using backtracking. The idea is to build the combinations incrementally, starting with an empty combination.

1. Sort candidates - although this step isn’t strictly necessary, it can help with pruning branches early.
2. Use a recursive function to explore each candidate:
   • Include the candidate in the current path.
   • Recur with the updated target reduced by the candidate’s value.
   • If the updated target is exactly 0, we have found a valid combination and append it to the results.
   • If the updated target is less than 0, we discard the current path.
   • After exploring, backtrack by removing the candidate from the current path to try the next candidate.

Let’s proceed to the implementation.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    void backtrack(std::vector<int>& candidates, int target, std::vector<int>& current, std::vector<std::vector<int>>& result, int start) {
        if (target == 0) {
            result.push_back(current);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) continue;
            
            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], current, result, i);
            current.pop_back();
        }
    }
    
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        std::sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, current, result, 0);
        return result;
    }
};

Time Complexity

The time complexity of this solution is a bit tricky to analyze due to the nature of the backtracking approach, but let’s consider some upper bounds:

• For each candidate, in the worst case, we try it multiple times (as many times as it can fit into the target).
• The average branching factor (rate at which recursion tree grows) is O(N) where N is the number of candidates.
• The depth of recursion is proportional to target / min(candidates), where min(candidates) is the smallest value in the candidates array.

Thus, the time complexity can be approximated by O(2^T * N), where T is the target and N is the number of candidates. This means the solution can handle small targets and smaller sets of candidates more efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?