Approach Recursive Method
Intuition
Most problems like this, which requires the return of all the required solutions, can be solved by recursive and the thinking part is similar.
if you carefully study these topics are found in a routine, are required to write another recursive function, I always named this function as 'helper'.
In this problem, we explain use problem example, where candidate set [2, 3, 6, 7] and target 7, and try to find the solution:
[
[7],
[2, 2, 3]
]
We can consider this problem as the problem to find a tree path where the sum of tree node value on this path
is equal to target.
As shown in the picture which starts from value 2, and we find a path in the tree which is [2, 2, 3]. How can we find the path like that?
Depth First Search !!!.
Generally, we use a stack to implement DFS, so the following code is like this:
Java
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
helper(candidates, target, 0, res, new ArrayList<>());
return res;
}
public void helper(int[] candidates, int tar, int start, List<List<Integer>> res, List<Integer> temp)
{
if(tar < 0) return;
else if(tar == 0) res.add(new ArrayList<>(temp));
else
{
for(int i = start; i<candidates.length;i++)
{
temp.add(candidates[i]);
helper(candidates, tarcandidates[i], i, res, temp);
temp.remove(temp.size()1);
}
}
}
}
Complexity Analysis

Time complexity : $O(n)$. where $n$ is the number of elements in the array. Because we have to visit all the tree node to get the path.

Space complexity : $O(log(n))$. The space complexity is related to the height of the 'Tree' which is $O(log(n))$
Can we do better?
Strategy
Every time we visit a node and we have to update the target value and then continue the recursive using the updated value.
But this case is not always necessary. Because when the node value which we visited is bigger than the target value
and we still doing the recursive is wasting time.
The modified code is as follows:
Java
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates, target, 0, res, new ArrayList<>());
return res;
}
public void helper(int[] candidates, int tar, int start, List<List<Integer>> res, List<Integer> temp)
{
if(tar < 0) return;
else if(tar == 0) res.add(new ArrayList<>(temp));
else
{
for(int i = start; i<candidates.length;i++)
{
if(candidates[i]>tar) break;
temp.add(candidates[i]);
helper(candidates, tarcandidates[i], i, res, temp);
temp.remove(temp.size()1);
}
}
}
}
Complexity Analysis

Time complexity : $O(n)$. where $n$ is the number of elements in the array. Because we have to visit all the tree node to get the path.

Space complexity : $O(log(n))$. The space complexity is related to the height of the 'Tree' which is $O(log(n))$