In this post, we explore a classic coding challenge from Leetcode: problem 39, “Combination Sum.” This problem tests a developer’s ability to find all possible combinations of elements in a given array that add up to a specific target value. We discuss the problem statement in detail, provide an example solution in JavaScript & Java, and discuss some key insights and tips for solving this problem effectively.
From Leetcode:
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: []
What is the problem asking?
The idea is to use backtracking. We start with an empty list and keep adding elements to it until we reach the target sum. We iterate over all the elements in the array and add them to the list if they don’t exceed the target sum.
We then recursively call the same function with the updated target sum and list. We keep doing this until we either reach the target sum or we run out of elements to add. We then remove the last element from the list and try adding the next element in the array.
We keep doing this until we either reach the target sum or we run out of elements to add. We keep doing this until we either reach the target sum or we run out of elements to add. We then return the list.
One thing to note is that we need to sort the array first in order for this approach to work. This is because, without sorting, there may be cases where we reach the target sum earlier but still have elements left in the array which can lead to duplicate combinations. By sorting the array, we ensure that all possible combinations are explored before moving on to the next element in the array.
Overall, this solution has a time complexity of O(n^m) where n is the length of the candidates array and m is the target sum. This is because at each step, we have n choices and we repeat this process m times until we reach the target sum. The space complexity is O(m) as at each step, we can potentially add a new combination to the output list.
Solving Leetcode 39 in Java:
class Solution {
public List < List < Integer >> combinationSum(int[] candidates, int target) {
List < List < Integer >> result = new ArrayList < > ();
if (candidates == null || candidates.length == 0) {
return result;
}
List < Integer > curr = new ArrayList < > ();
dfs(candidates, target, 0, curr, result);
return result;
}
private void dfs(int[] candidates, int target, int index, List < Integer > curr, List < List < Integer >> result) {
if (target == 0) {
result.add(new ArrayList < > (curr));
return;
}
for (int i = index; i < candidates.length; i++) {
if (target - candidates[i] >= 0) {
curr.add(candidates[i]);
dfs(candidates, target - candidates[i], i, curr, result);
curr.remove(curr.size() - 1);
}
}
}
}
Solution in JavaScript:
const combinationSum = (candidates, target) => {
const res = [];
const dfs = (start, sum, path) => {
if (sum > target) return;
if (sum === target) {
res.push(path.slice());
return;
}
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]);
dfs(i, sum + candidates[i], path);
path.pop();
}
};
dfs(0, 0, []);
return res;
};
LeetCode 39 problem is a great challenge for any coding enthusiast. By using a combination of backtracking and recursion, the problem can be solved efficiently. While this approach may not be the most straightforward solution, it is an effective way to find all possible combinations of integers that add up to the target number. With a bit of practice, it can be a great tool to help you master the basics of coding.
Similar Questions:
- Combinations