Combination sum-1

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The problem "Combination Sum" on LeetCode requires designing an algorithm to find all unique combinations in a given array of positive integers candidates where the candidate numbers sum up to a specified target number. Each candidate number can be used an unlimited number of times. The problem claims a target can always be achieved if it exists.

Here's a simplified version of the problem statement:

  • You are given an array candidates of distinct positive integers and a target integer target.
  • Return all unique combinations of candidates where the chosen numbers sum to target.
  • You may return the combinations in any order.
  • The same number from candidates may be used unlimited times in the combination.

Understanding the Problem

This problem is a classic example of the "subset sum" problem, which can be tackled using a recursive backtracking approach. Since a number can be used multiple times, it's essential to consider the same index again after including a candidate number in a combination.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
- 2 + 2 + 3 = 7
- 7 = 7
No other combinations of candidates can sum up to target 7.

Key DSA Concepts and Theory

Recursion and Backtracking

Recursion involves solving a problem by solving smaller instances of the same problem. It helps simplify the code, though it may be less intuitive to some. Here, recursion is useful for exploring each path in the solution space.

Backtracking is an algorithmic technique for solving constraint satisfaction problems. It incrementally builds candidates to the solution and abandons a candidate ("backtracks") as soon as it's determined that this candidate cannot lead to a valid solution.

In this problem, backtracking is used to:

  1. Explore all potential combinations.
  2. Track the sum of combinations.
  3. Abandon paths that exceed the target.

Solution Approach

Step-by-Step Explanation

  1. Sorting (Optional): Sort the candidates array to make pruning more efficient (optional but can help optimize the search).

  2. Recursive Function: Implement a recursive function that explores all combinations.

  3. Base Case: If the target is met, add the current combination to the result list.

  4. Iterate and Recur: Iterate through candidates; for each candidate:

    • Include it in the current path.
    • Recursively explore with reduced target (target - candidate).
    • Backtrack by removing the candidate from the path.

  5. Avoid Duplicate Combinations: Ensure combinations are built in a non-decreasing order (by using current index and not moving backward).

Code Implementation

C++ Solution

#include <vector>
#include <algorithm>

class Solution {
public:
    void backtrack(std::vector<int>& candidates, int target, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (target < 0) return;     // Base case: If the remaining target is negative, discard this path
        if (target == 0) {          // If the current path adds up to the target, add it to the result
            result.push_back(current);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i, current, result); // Recurse without incrementing start to allow unlimited use of the same number
            current.pop_back(); // Backtrack
        }
    }

    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }
};

Java Solution

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

public class Solution {
    public void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target < 0) return;  // Base case
        if (target == 0) {       // Successful combination
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, current, result); // i and not i + 1, as we can reuse same elements
            current.remove(current.size() - 1); // Backtrack
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
}

Time and Space Complexity Analysis

  • Time Complexity: The time complexity is approximately O(N^(T/M + 1)), where N is the number of candidates, and T is the target, and M is the smallest candidate value. This is because each path in the solution tree can have a depth of T/M, and there are potentially N branches at each step.

  • Space Complexity: O(T/M), where the space is primarily due to the recursion stack space.

Common Mistakes to Avoid

  1. Incorrect Base Case: Ensure to handle the base case where target sum hits zero promptly.
  2. Repeated Combinations: Use indices correctly to avoid considering previously added candidates again.
  3. Mutable States: Don't forget to remove elements (backtrack) from the current combination before exploring other paths.

Similar Problems on LeetCode

  • Combination Sum II (Problem 40) - Similar problem but each candidate may only be used once.
  • Combination Sum III (Problem 216) - Find all valid combinations with fixed length.
  • Subsets (Problem 78) - Generating all subsets of a given set.
  • Permutations (Problem 46) - Generating all permutations of a sequence.

Additional Resources and References

This article should equip you with the foundational steps and practices to solve the Combination Sum problem efficiently using recursion and backtracking. Happy coding!