39. Combination Sum

Published on April 17, 2023

Question

Given a candidates and a target, find all the combination of the candidates which sum of all the elements equals to the target.

Algorithm

First you might think we could find all the combination and then traverse each of them to see if the sum of them is target. This will introduce extra complex.

This is a question based on the combination of an array. We follow the same pattern of getting the combination.We could do it when we doing backtracking, it's a DFS procedure and we are adding the elements one by one, so we could maintain a sum, the end of the recursion is sum == target.

Code

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return res;
        }
        
        helper(res, candidates, 0, target, new ArrayList<>(), 0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, int[] candidates, int index, int target, List<Integer> list, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(list));
            return;
        } else if (sum < target) {
            for (int i = index; i < candidates.length; i++) {
                list.add(candidates[i]);
                helper(res, candidates, i, target, list, sum + candidates[i]);
                list.remove(list.size() - 1);
            }
        }
    }
}