Backtracking.java

import java.util.*;
public class Backtracking {
    public List<List<Integer>> backtracking(int[] candidates, int target){
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(),result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0) return;

        for (int i = start; i < candidates.length; i++){
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args){
        Backtracking cs = new Backtracking();
        int[] candidates = {2,3,6,7};
        int target = 7;
        System.out.println(cs.backtracking(candidates, target));
    }
    
}