Combination Sum with Restrictions — Problem Statement & Solution Guide

BacktrackingMediumMixed

TimeO(2^n * k) // k = average length of a valid combination

SpaceO(n) // recursion stack + current path

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Backtracking and solve the Combination Sum with Restrictions problem optimally.

TopicBacktracking

PatternMixed

TimeO(2^n * k) // k = average length of a valid combination

SpaceO(n) // recursion stack + current path

Problem Description

Given an integer array asteroids and an integer targetGems, return every distinct combination of elements from asteroids whose sum equals targetGems. Each element may be chosen at most once, and the multiplicity of a value is limited by its occurrences in the input array. The order of numbers inside a combination does not matter, and the set of combinations must not contain duplicates. Return the list of combinations in any order; each combination should be presented as a list of its values sorted in non‑decreasing order.

DSA Pattern Breakdown

"Combination Sum with Restrictions"

medium

WHY DOES IT MATTER?

Backtracking is essential for problems that require enumerating all feasible subsets under combinatorial constraints, because it systematically explores the solution space while discarding impossible paths early, preventing exponential blow‑up.

OPTIMIZATION CHALLENGE

The key insight is to sort the array and skip over duplicate values at the same recursion depth, which guarantees uniqueness of combinations and dramatically cuts down redundant work.

REAL-WORLD CONNECTION

Think of a distributed job scheduler that tries different node allocations to meet a resource quota; each allocation attempt is a branch, and the scheduler aborts any allocation that exceeds the quota, similar to pruning in backtracking.

During an interview, explicitly state the sorting step, the duplicate‑skip condition, and the pruning condition before writing code; this shows you understand both correctness and performance.

COMPLEXITY AT A GLANCE

⏱ Time:O(2^n * k) // k = average length of a valid combination

💾 Space:O(n) // recursion stack + current path

Core Theory — Why This Approach?

Backtracking is a depth‑first search technique that incrementally builds candidate solutions and abandons a path (“backtracks”) as soon as it determines that this path cannot possibly lead to a valid answer. For the "Combination Sum with Restrictions" problem we first sort the input array so that equal values become adjacent; this makes it easy to skip duplicates and respect the multiplicity constraint. The recursive routine then iterates over the remaining elements, chooses the current element, and recurses with a reduced target (targetGems − currentValue) and a next‑index that moves past the chosen element, guaranteeing each number is used at most once. Whenever the running sum matches the target, we record a copy of the current path as a distinct combination.

A naïve brute‑force solution would enumerate every subset of the array (2^n possibilities) and sum each subset to check against the target. This approach quickly becomes infeasible for n ≥ 30 because the exponential blow‑up overwhelms both time and memory. Moreover, without careful duplicate handling, the naïve method would produce repeated combinations when the input contains repeated values. The optimal backtracking paradigm eliminates large swaths of the search space early by pruning any branch whose partial sum exceeds the target, and by skipping over identical values at the same recursion depth. This reduces the effective branching factor and ensures that each unique combination is generated exactly once, yielding a solution that scales much better in practice.

The combination of sorting, duplicate‑skip logic, and early pruning embodies the classic "subset‑sum" backtracking pattern. It leverages the problem’s constraints (each element used once, limited multiplicity) to transform an exponential‑time brute force into a tractable search that runs in O(2^n · k) where k is the average length of a valid combination, and uses O(n) auxiliary space for the recursion stack and current path.

Interview Questions on This Problem

Q1How would you modify the backtracking solution if each number could be used unlimited times (i.e., the classic Combination Sum problem)?

Allow the recursive call to reuse the current index instead of moving to the next one, so the same element can be chosen multiple times; also remove the duplicate‑skip logic that depends on sorted adjacent values.

Q2In a fintech platform, why might you prefer a backtracking solution over a DP table for a variant of the subset‑sum problem with strict usage limits?

When the input size is moderate but the number of distinct values is high, DP tables can become memory‑intensive; backtracking with pruning uses only O(n) space and can stop early when the sum exceeds the target, which is valuable for latency‑sensitive financial calculations.

Q3What is the impact of sorting the input array on both time complexity and duplicate handling in this problem?

Sorting costs O(n log n) upfront but enables linear‑time duplicate skipping during recursion and allows early termination of branches when the remaining numbers are too large, effectively reducing the number of recursive calls.

Examples

Example 1

Input

{"asteroids":[2,3,5,2],"targetGems":7}

Output

[[2,5],[2,2,3]]

Explanation: The array contains two copies of 2. Using one 2 with 5 gives 7, and using both 2’s together with 3 also gives 7. No other subset sums to 7, and each element is used no more than its available count.

Example 2

Input

{"asteroids":[1,1,1,2,2],"targetGems":4}

Output

[[1,1,2],[2,2]]

Explanation: Possible subsets that sum to 4 are: pick two 1’s and one 2 (there are three 1’s, so any pair works) or pick the two 2’s. Subsets like [1,1,1,1] are impossible because only three 1’s exist.

Example 3

Input

{"asteroids":[10,1,2,7,6,1,5],"targetGems":8}

Output

[[1,1,6],[1,2,5],[1,7],[2,6]]

Explanation: After sorting the array, backtracking explores each element once. Valid sums are: - 1 + 1 + 6 = 8 (using both 1’s), - 1 + 2 + 5 = 8, - 1 + 7 = 8, - 2 + 6 = 8. All other subsets either exceed 8 or reuse an element more times than it appears.

Constraints

1 <= asteroids.length <= 30
-10^4 <= asteroids[i] <= 10^4
1 <= targetGems <= 10^5
The total number of distinct combinations fits in memory for the given limits.

Optimal Approach & Strategy

Use sorted backtracking with duplicate skipping and early pruning: recurse only while the running sum ≤ target, and skip identical values at the same depth to ensure uniqueness.

Brute Force Approach

Generate every possible subset of the array and check if its sum equals targetGems; this requires exploring 2^n subsets and is impractical for large n.

Code Solutions

Language:

JavaScript Solution

Time: O(2^n * k) // k = average length of a valid combination

/**
 * @param {number[]} asteroids
 * @param {number} targetGems
 * @return {number[][]}
 */
var combinationSum = function(asteroids, targetGems) {
    const result = [];
    const current = [];
    asteroids.sort((a, b) => a - b);
    
    const backtrack = (start, remaining) => {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        if (remaining < 0) return;
        
        for (let i = start; i < asteroids.length; i++) {
            // Skip duplicates at the same level
            if (i > start && asteroids[i] === asteroids[i - 1]) continue;
            
            // Prune: if current element makes sum exceed target, break
            if (asteroids[i] > remaining) break;
            
            current.push(asteroids[i]);
            backtrack(i + 1, remaining - asteroids[i]);
            current.pop();
        }
    };
    
    backtrack(0, targetGems);
    return result;
};

// Example usage
const asteroids = [2, 5, 2, 1, 2];
const targetGems = 7;
const result = combinationSum(asteroids, targetGems);
console.log(result);

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& asteroids, int targetGems) {
        vector<vector<int>> result;
        vector<int> current;
        sort(asteroids.begin(), asteroids.end());
        
        function<void(int, int)> backtrack = [&](int start, int remaining) {
            if (remaining == 0) {
                result.push_back(current);
                return;
            }
            if (remaining < 0) return;
            
            for (int i = start; i < asteroids.size(); ++i) {
                // Skip duplicates at the same level
                if (i > start && asteroids[i] == asteroids[i - 1]) continue;
                
                // Prune: if current element makes sum exceed target, break
                if (asteroids[i] > remaining) break;
                
                current.push_back(asteroids[i]);
                backtrack(i + 1, remaining - asteroids[i]);
                current.pop_back();
            }
        };
        
        backtrack(0, targetGems);
        return result;
    }
};

int main() {
    vector<int> asteroids = {2, 5, 2, 1, 2};
    int targetGems = 7;
    Solution sol;
    vector<vector<int>> result = sol.combinationSum(asteroids, targetGems);
    
    for (const auto& combo : result) {
        for (int i = 0; i < combo.size(); ++i) {
            cout << combo[i];
            if (i < combo.size() - 1) cout << ",";
        }
        cout << "\n";
    }
    return 0;
}

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] asteroids, int targetGems) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        Arrays.sort(asteroids);
        
        backtrack(asteroids, targetGems, 0, 0, current, result);
        return result;
    }
    
    private void backtrack(int[] asteroids, int target, int start, int currentSum, 
                           List<Integer> current, List<List<Integer>> result) {
        if (currentSum == target) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (currentSum > target) return;
        
        for (int i = start; i < asteroids.length; i++) {
            // Skip duplicates at the same level
            if (i > start && asteroids[i] == asteroids[i - 1]) continue;
            
            // Prune: if current element makes sum exceed target, break
            if (asteroids[i] > target - currentSum) break;
            
            current.add(asteroids[i]);
            backtrack(asteroids, target, i + 1, currentSum + asteroids[i], current, result);
            current.remove(current.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        int[] asteroids = {2, 5, 2, 1, 2};
        int targetGems = 7;
        Solution sol = new Solution();
        List<List<Integer>> result = sol.combinationSum(asteroids, targetGems);
        for (List<Integer> combo : result) {
            System.out.println(combo);
        }
    }
}

from typing import List

class Solution:
    def combinationSum(self, asteroids: List[int], targetGems: int) -> List[List[int]]:
        result = []
        current = []
        asteroids.sort()
        
        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            if remaining < 0:
                return
            
            for i in range(start, len(asteroids)):
                # Skip duplicates at the same level
                if i > start and asteroids[i] == asteroids[i - 1]:
                    continue
                
                # Prune: if current element makes sum exceed target, break
                if asteroids[i] > remaining:
                    break
                
                current.append(asteroids[i])
                backtrack(i + 1, remaining - asteroids[i])
                current.pop()
        
        backtrack(0, targetGems)
        return result

# Example usage
if __name__ == "__main__":
    asteroids = [2, 5, 2, 1, 2]
    targetGems = 7
    sol = Solution()
    result = sol.combinationSum(asteroids, targetGems)
    print(result)

/**
 * @param {number[]} asteroids
 * @param {number} targetGems
 * @return {number[][]}
 */
var combinationSum = function(asteroids, targetGems) {
    const result = [];
    const current = [];
    asteroids.sort((a, b) => a - b);
    
    const backtrack = (start, remaining) => {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        if (remaining < 0) return;
        
        for (let i = start; i < asteroids.length; i++) {
            // Skip duplicates at the same level
            if (i > start && asteroids[i] === asteroids[i - 1]) continue;
            
            // Prune: if current element makes sum exceed target, break
            if (asteroids[i] > remaining) break;
            
            current.push(asteroids[i]);
            backtrack(i + 1, remaining - asteroids[i]);
            current.pop();
        }
    };
    
    backtrack(0, targetGems);
    return result;
};

// Example usage
const asteroids = [2, 5, 2, 1, 2];
const targetGems = 7;
const result = combinationSum(asteroids, targetGems);
console.log(result);

Asked in Top Tech Interviews

Atlassian

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.