grid47 Exploring patterns and algorithms
Nov 3, 2024
6 min read
Solution to LeetCode 39: Combination Sum Problem
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 can 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.
Problem
Approach
Steps
Complexity
Input: You are given an array of distinct integers candidates and a target integer target.
• Explanation: For this example, the unique combinations that sum to 15 are: [5, 5, 5], [7, 7], and [5, 10].
Approach: We can use backtracking to explore all possible combinations, while ensuring we don’t use the same combination more than once.
Observations:
• We can use recursion to explore all combinations, adding numbers to a temporary list and checking if we’ve reached the target sum.
• Using backtracking will allow us to explore all possible combinations and backtrack if the sum exceeds the target.
Steps:
• Sort the input array of candidates.
• Use a recursive function to explore combinations of numbers that sum to the target.
• At each step, either include the current candidate in the combination or move on to the next one.
• If a combination matches the target, add it to the result.
Empty Inputs:
• If the input array is empty, return an empty result since no combinations can be formed.
Large Inputs:
• Even with the upper limit of input size (candidates.length <= 30), the problem ensures fewer than 150 unique combinations, so performance should be manageable.
Special Values:
• If the target is smaller than the smallest candidate, return an empty list.
Constraints:
• Ensure no duplicate combinations are added to the result.
vector<vector<int>> combinationSum(vector<int>& cand, int target) {
This line declares a function named `combinationSum` that takes a vector of candidate numbers `cand` and a target number `target` as input and returns a vector of vectors representing all possible combinations of numbers from `cand` that add up to `target`.
2 : Vector Initialization
vector<vector<int>> ans;
This line initializes an empty 2D vector `ans` to store the resulting combinations.
3 : Vector Initialization
vector<int> tmp;
This line initializes an empty vector `tmp` to store a temporary combination during the backtracking process.
4 : Function Call
bt(ans, tmp, 0, target, cand);
This line calls the helper function `bt` to perform the backtracking process. The `ans`, `tmp`, `0`, `target`, and `cand` are passed as arguments.
5 : Return
return ans;
This line returns the `ans` vector containing all the valid combinations.
6 : Function Declaration
voidbt(vector<vector<int>>&ans, vector<int>&tmp, int idx, int sum, vector<int>&cand) {
This line declares a recursive backtracking function `bt` that takes the following parameters: `ans` to store the result, `tmp` to store the current combination, `idx` to track the current index in the `cand` vector, `sum` representing the remaining target sum, and `cand` the vector of candidate numbers.
This block checks the base cases: 1. If the index `idx` reaches the end of the `cand` vector or the `sum` becomes 0, it means we've reached a valid combination. If `sum` is 0, the current `tmp` combination is added to the `ans` vector. 2. In either case, the function returns to the previous recursive call.
8 : Pruning
if(sum <0) return;
This line prunes the search space by checking if the `sum` becomes negative. If so, it means the current path cannot lead to a valid combination, so the function returns early.
9 : Include the Current Candidate
tmp.push_back(cand[idx]);
This line adds the current candidate number `cand[idx]` to the `tmp` combination.
10 : Recursive Call (Include)
bt(ans, tmp, idx, sum - cand[idx], cand);
This line recursively calls the `bt` function with the updated `sum` (reduced by the current candidate) to explore the possibility of including the current candidate in the combination.
11 : Backtrack
tmp.pop_back();
This line removes the last added candidate from the `tmp` combination to backtrack to the previous state.
12 : Recursive Call (Exclude)
bt(ans, tmp, idx +1, sum, cand);
This line recursively calls the `bt` function with the same `sum` but the next index `idx + 1` to explore the possibility of excluding the current candidate from the combination.
Best Case: O(N^2)
Average Case: O(N^2)
Worst Case: O(2^N)
Description: The worst case complexity arises from the backtracking approach, where each number is considered in each recursive step.
Best Case: O(1)
Worst Case: O(N)
Description: Space complexity depends on the depth of the recursion tree and the size of the temporary storage used for combinations.
