https://leetcode.com/problems/combination-sum/
initial
backtracking but we need to realise the diff between
dfs(so_far, sum, i, target, nums) and dfs(so_far, sum, 0, target, nums)
where i=index in for loop.
If we pass the current index to the loop, we are makigng sure its not permutation and we iter only from current_index to end of list instead of 0 to end of list.
sol
class Solution {
public List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<Integer> tmp = new ArrayList<>();
dfs(tmp,0,0,target,nums);
return ans;
}
public void dfs(List<Integer> so_far, int sum, int index, int target, int[] nums){
if(sum>target) return;
if(sum==target){
ans.add(new ArrayList<>(so_far));
return;
}
for(int i=index;i<nums.length; i++){
so_far.add(nums[i]);
sum+=nums[i];
dfs(so_far,sum,i,target,nums);
so_far.remove(so_far.size()-1);
sum-=nums[i];
}
}
}complexity
n 2^n time? yes
2n space? no main space is the recursion depth which is n
