Combination Sum

import java.util.*;
public class Main
{
	public static void main(String[] args) {
		int[] arr = {2,3,5};
		System.out.println(combinationSum(arr, 8));
	}
	
	public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ds = new ArrayList<>();
        helper(0, candidates, target, ans, ds);
        return ans;
    }
    
    public static void helper(int index, int[] arr, int target, List<List<Integer>> ans, List<Integer> ds) {
        if(index==arr.length) {
            if(target==0) {
                ans.add(new ArrayList<>(ds));
            }
            return;
        }
        
        if(arr[index] <= target) {
            ds.add(arr[index]);
            helper(index, arr, target-arr[index], ans, ds);
            ds.remove(ds.size()-1);
        }
        
        helper(index+1, arr, target, ans, ds);
    }
}

Combination Sum (Python)

def combinationSum(candidates, target):
    ds = []
    helper(0, candidates, target, ds)
    
def helper(index, candidates, target, ds):
    if index==len(candidates):
        if target==0:
            print(ds)
        return
        
    if candidates[index] <= target:
        ds.append(candidates[index])
        helper(index, candidates, target-candidates[index], ds)
        del ds[-1]
        
    helper(index+1, candidates, target, ds)
        
candidates = [1,2,3,4,5]
combinationSum(candidates, 5)

Leave a Comment