The link to the problem: https://leetcode.com/problems/combination-sum/
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.
The same number may be chosen from candidates an unlimited number of times.
Example: for candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]Thoughts:
This is a typical backtracking problem. We always need to make a choice, then see what other choices we can make after making the choice, and keep going until we reach the target OR stop making choice when we found that it is a dead-end.
Code Logic (with Graph and Example):
I will first sort the candidates array since if we sort it, we can avoid traversing the “unneeded choices”.
Let us first use the above example to explain how we do backtracking.
The reason why we call backtracking is that we keep traversing down (i.e., make choices). If we found a dead-end, we undo the current choice and back to the previous choice to choose another one.
Below is the diagram that I made to visualize the backtracking idea for this example.
We use an inner list to store the choices.
(A) At the very initial point, the target is 7, and the inner list is empty.
(B) First, we choose 2 and the target is 5 now. (💡 inner list: [2])
(C) Then we choose 2 again and the target is 3. (💡 inner list: [2,2])
(D) Choose 2 again and the target is 1. (💡 inner list: [2,2,2])
(E) Then we found that this is a dead-end since the choices are all bigger than the target.
Redo the choice that we made at level D, so we drop the last element in the inner list. (💡 now inner list: [2,2]) The target is 3.
(D) We choose 3 this time and the target is 0. (💡 inner list: [2,2,3]) → BINGO, we add this inner list to our result list!
(E) Since the target is 0 now, we don’t need to keep going. (since all the candidates are positive)
Redo the choice that we made at level D, so we drop the last element in the inner list. (💡 now inner list: [2,2]) The target is 3.
(D) we can’t choose 6 since it is greater than the target, and because we sort the array first, we know the elements after 6 are also dead-end. We are done.
Now we have done the paths when the inner list starts with [2,2].
Redo the choice we made at level C. (💡 now inner list: [2]) The target is 5.
(C) We choose 3 this time and the target is 2. (💡 inner list:[2,3])
(D) We only have 3 choices and the first choice — 3 is bigger than the target. Dead-end here so we give up this path.
(⚠️ original candidates array has 4 elements but since the order in this combination problem doesn’t matter, we should not pick the element before the current element to prevent duplicate inner list! )
Redo the choice we made at Level C. (💡 now inner list:[2]) The target is 5.
(C) We can’t choose 6 since it is larger than the target. Dead-end here.
Redo the choice we made at level B. (💡 now inner list:[]) The target is 7.
(B) Choose 3, and the target is 4. (💡 inner list: [3])
(C) Choose 3 again, and the target is 1. (💡 inner list: [3,3])
(D) Dead-end.
Redo the choice we made at level C. (💡 now inner list:[3]) The target is 4.
(C) We can’t choose 6 since it is larger than the target. Dead-end here
Redo the choice we made at level B. (💡 now inner list:[]) The target is 7.
(B) Choose 6, and the target is 1. (💡 inner list: [6])
(C) Dead-end.
Redo the choice we made at level B. (💡 now inner list:[]) The target is 7.
(B) Choose 7, and the target is 0. (💡 inner list: [7]) → BINGO, we add this inner list to our result list!
Redo the choice we made at level B. (💡 now inner list:[]) The target is 7.
No other choices now. So we’re DONE! 😴 The result list now has two inner lists and that’s our answer!
⚠️ It is recommended to practice a similar diagram yourself to know better the idea of backtracking! 💪
Below is the 2ms code that beats 98%:
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> rst = new ArrayList<>();
helper(rst,new ArrayList<>(),candidates,0,target);
return rst;
}
public void helper(List<List<Integer>> rst, List<Integer> inner, int[] arr, int indx, int target){
if(target==0)
{
rst.add(new ArrayList<>(inner));
return;
}
for(int i=indx;i<arr.length;i++)
{
if(arr[i]>target) //eliminate unneeded paths
return;
inner.add(arr[i]); //select our choice
helper(rst,inner, arr, i, target-arr[i]);
inner.remove(inner.size()-1); //redo
}
}Both time Complexity and space complexity are exponential since we need to keep finding the possible combination.
✏️After knowing the idea of how to solve this problem, you can also try to solve 78. Subsets yourself! 👊
