[Leetcode] 39. Combination Sum

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];
        }
    }
}

with py, u can use list() or result_so_far[:] to make a copy.

class Solution:
    def combinationSum(self, nums: list[int], target: int) -> list[list[int]]:
        ans = []
        
        def dfs(index, current_sum, so_far):
            # Base Case: exceeded target
            if current_sum > target:
                return
            
            # Base Case: reached target
            if current_sum == target:
                ans.append(list(so_far)) # Create a copy of the current path
                return
            
            # Recursive step: try candidates starting from 'index'
            # (Using 'index' allows us to reuse the same number multiple times)
            for i in range(index, len(nums)):
                so_far.append(nums[i])
                # Note: we pass i as the next index to allow reuse of nums[i]
                dfs(i, current_sum + nums[i], so_far)
                # Backtrack
                so_far.pop()

        dfs(0, 0, [])
        return ans

complexity

n 2^n time? yes
2n space? no main space is the recursion depth which is n