algoadvance

Leetcode 39. Combination Sum

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

Clarifying Questions

  1. Can the input array contain negative numbers?
    • No, candidates array contains only positive integers as per the constraints.
  2. Should the combination lists be in a specific order?
    • No, the combinations can be returned in any order.
  3. Is there any restriction on the number of times a candidate can be chosen?
    • No, the same candidate can be chosen multiple times.

Strategy

  1. Backtracking Approach:
    • Use backtracking to explore all potential combinations.
    • For each candidate, decide to include it in the current combination or skip to the next candidate.
    • If the current sum exceeds the target, backtrack.
    • If the current sum equals the target, add the current combination to the result list.

Code

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(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 remain, int start, List<Integer> tempList, List<List<Integer>> result) {
        if (remain < 0) {
            return; // if the remaining sum is negative, there's no point in continuing
        } else if (remain == 0) {
            result.add(new ArrayList<>(tempList)); // if remaining sum is zero, add the combination to result
        } else {
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]);
                backtrack(candidates, remain - candidates[i], i, tempList, result); // not i + 1 because we can reuse same elements
                tempList.remove(tempList.size() - 1); // undo the last action
            }
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        System.out.println(cs.combinationSum(new int[]{2, 3, 6, 7}, 7));
        System.out.println(cs.combinationSum(new int[]{2, 3, 5}, 8));
        System.out.println(cs.combinationSum(new int[]{2}, 1));
    }
}

Time Complexity

The time complexity is O(2^t * k), where t is the target value and k is the average length of each combination. Here, we are exploring all possible combinations, and in the worst case, we might recurse for every number up to the target value.

The space complexity is O(k), where k is the depth of the recursion tree, which is determined by the length of the combination.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI