Galactic Cargo Router — Problem Statement & Solution Guide

RecursionMediumMixed

TimeO(2^n) worst‑case, but proportional to the number of valid combinations times their length due to pruning

SpaceO(n) recursion stack plus O(C·k) for storing C output combinations of average size k

Problem Description

Given an array weights of positive integers representing the mass of each cargo crate and an integer capacity denoting the maximum load a spaceship can carry, write a recursive function that returns every distinct combination of crates whose total weight equals capacity. Each crate may be selected at most once. The order of crates inside a combination is irrelevant, and the output must not contain duplicate combinations. Return the result as a list of lists, where each inner list is a valid combination sorted in non‑decreasing order.

DSA Pattern Breakdown

"Galactic Cargo Router"

medium

WHY DOES IT MATTER?

Backtracking with duplicate‑skip is essential for any problem that asks for all unique subsets because it prevents exponential blow‑up caused by repeated elements and ensures result correctness without post‑processing.

OPTIMIZATION CHALLENGE

The key insight is sorting the array and, during recursion, skipping over consecutive equal weights when they appear at the same depth; this eliminates duplicate branches early and dramatically cuts both time and memory usage.

REAL-WORLD CONNECTION

Think of loading cargo onto a shuttle: each crate can be placed once, and you must find every feasible loading plan that exactly fills the shuttle’s weight limit—mirroring how distributed systems schedule tasks to exactly fill resource quotas without over‑provisioning.

When coding in an interview, sort first, then write a helper that takes (startIndex, remainingCapacity, currentPath); always check "if i>start && weights[i]==weights[i-1]" to skip duplicates before recursing.

COMPLEXITY AT A GLANCE

⏱ Time:O(2^n) worst‑case, but proportional to the number of valid combinations times their length due to pruning

💾 Space:O(n) recursion stack plus O(C·k) for storing C output combinations of average size k

Core Theory — Why This Approach?

The problem is a classic variant of the Subset Sum / Combination Sum II problem, where we must enumerate every unique subset of a multiset that adds up to a target value. A naive recursive enumeration that tries every inclusion/exclusion choice yields 2^n possibilities, which quickly becomes infeasible for n>30. By first sorting the input array we can prune branches when the running sum exceeds the capacity and, crucially, skip over duplicate values at the same recursion depth, guaranteeing each distinct combination appears exactly once. This backtracking paradigm leverages depth‑first search with stateful indices, turning an exponential‑time brute force into a tractable solution for typical interview constraints while still being optimal for the output‑sensitive nature of the task.

Interview Questions on This Problem

Q1How would you modify the recursive solution to return the count of distinct combinations instead of the combinations themselves?

Maintain a global counter and increment it each time the recursion reaches a sum equal to capacity; you can still prune duplicates by sorting and skipping equal values at the same depth.

Q2What is the time complexity of generating all combinations for an input of size n where k is the size of each valid combination?

In the worst case the algorithm explores O(2^n) subsets, but the actual work is proportional to the number of valid combinations times their average length, i.e., O(C·k) where C is the output size.

Q3If the weights array can contain up to 10^5 elements but the capacity is small (≤100), which technique would you choose and why?

Use dynamic programming (DP) with a bitset or memoized recursion that tracks achievable sums up to capacity; the DP runs in O(n·capacity) time and O(capacity) space, which is far better than exponential backtracking for large n with small target.

Examples

Example 1

Input

weights = [2,3,5,7], capacity = 10

Output

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

Explanation: Start with an empty combination. Choose 2 → remaining 8, then 3 → remaining 5, then 5 → remaining 0 → record [2,3,5]. Backtrack, skip 5, choose 7 with 3 → remaining 0 → record [3,7]. No other selections reach exactly 10, so the final list is [[2,3,5],[3,7]].

Example 2

Input

weights = [1,2,2,3], capacity = 5

Output

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

Explanation: Sorted weights are [1,2,2,3]. Selecting 1 leaves 4; picking the first 2 leaves 2; picking the second 2 reaches 0 → record [1,2,2]. Backtrack to after 1, skip first 2, pick second 2 leaves 3; then pick 3 reaches 0 → record [2,3]. All other paths either exceed or cannot reach 5, yielding [[1,2,2],[2,3]].

Example 3

Input

weights = [4,6,8], capacity = 3

Output

[]

Explanation: All crate weights exceed the target capacity of 3, so no combination can sum to 3. The function returns an empty list.

Constraints

1 <= weights.length <= 20
1 <= weights[i] <= 100
1 <= capacity <= 500
All numbers are integers

Optimal Approach & Strategy

Sort the array and use backtracking with early sum pruning and duplicate‑skipping to explore only viable branches and produce each distinct combination once.

Brute Force Approach

Generate every subset of the array (2^n possibilities) and filter those whose sum equals capacity, then deduplicate the results.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(2^n) worst‑case, but proportional to the number of valid combinations times their length due to pruning

function cargoRouter(weights, capacity) {
    weights.sort((a,b)=>a-b);
    const result = [];
    function backtrack(start, target, path){
        if(target===0){
            result.push([...path]);
            return;
        }
        if(target<0) return;
        for(let i=start;i<weights.length;i++){
            if(i>start && weights[i]===weights[i-1]) continue; // skip duplicates
            if(weights[i]>target) break;
            path.push(weights[i]);
            backtrack(i+1, target-weights[i], path);
            path.pop();
        }
    }
    backtrack(0, capacity, []);
    return result;
}
// Driver (Node.js) – same as template, omitted for brevity

#include <bits/stdc++.h>
using namespace std;
void backtrack(const vector<int>& w, int idx, int target, vector<int>& cur, vector<vector<int>>& ans){
    if(target==0){
        ans.push_back(cur);
        return;
    }
    if(target<0 || idx==(int)w.size()) return;
    // include w[idx]
    cur.push_back(w[idx]);
    backtrack(w, idx+1, target-w[idx], cur, ans);
    cur.pop_back();
    // skip duplicates at same recursion level
    int next=idx+1;
    while(next<(int)w.size() && w[next]==w[idx]) ++next;
    backtrack(w, next, target, cur, ans);
}
vector<vector<int>> cargoRouter(const vector<int>& weights, int capacity){
    vector<int> sorted = weights;
    sort(sorted.begin(), sorted.end());
    vector<vector<int>> ans;
    vector<int> cur;
    backtrack(sorted, 0, capacity, cur, ans);
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> weights(n);
    for(int i=0;i<n;++i) cin>>weights[i];
    int capacity; cin>>capacity;
    auto res = cargoRouter(weights, capacity);
    cout<<"[";
    for(size_t i=0;i<res.size();++i){
        cout<<"[";
        for(size_t j=0;j<res[i].size();++j){
            cout<<res[i][j];
            if(j+1<res[i].size()) cout<<",";
        }
        cout<<"]";
        if(i+1<res.size()) cout<<",";
    }
    cout<<"]\n";
    return 0;
}

import java.util.*;
public class Main {
    public static List<List<Integer>> cargoRouter(int[] weights, int capacity) {
        Arrays.sort(weights);
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(weights, 0, capacity, new ArrayList<>(), ans);
        return ans;
    }
    private static void backtrack(int[] w, int idx, int target, List<Integer> cur, List<List<Integer>> ans){
        if(target==0){
            ans.add(new ArrayList<>(cur));
            return;
        }
        if(target<0 || idx==w.length) return;
        // include w[idx]
        cur.add(w[idx]);
        backtrack(w, idx+1, target-w[idx], cur, ans);
        cur.remove(cur.size()-1);
        // skip duplicates
        int next = idx+1;
        while(next<w.length && w[next]==w[idx]) next++;
        backtrack(w, next, target, cur, ans);
    }
    // main method same as template, omitted for brevity
}

def cargo_router(weights, capacity):
    weights.sort()
    result = []
    def backtrack(start, target, path):
        if target == 0:
            result.append(path.copy())
            return
        if target < 0:
            return
        i = start
        while i < len(weights):
            if i > start and weights[i] == weights[i-1]:
                i += 1
                continue
            if weights[i] > target:
                break
            path.append(weights[i])
            backtrack(i+1, target-weights[i], path)
            path.pop()
            i += 1
    backtrack(0, capacity, [])
    return result

function cargoRouter(weights, capacity) {
    weights.sort((a,b)=>a-b);
    const result = [];
    function backtrack(start, target, path){
        if(target===0){
            result.push([...path]);
            return;
        }
        if(target<0) return;
        for(let i=start;i<weights.length;i++){
            if(i>start && weights[i]===weights[i-1]) continue; // skip duplicates
            if(weights[i]>target) break;
            path.push(weights[i]);
            backtrack(i+1, target-weights[i], path);
            path.pop();
        }
    }
    backtrack(0, capacity, []);
    return result;
}
// Driver (Node.js) – same as template, omitted for brevity

Asked in Top Tech Interviews

Adobe

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.

Galactic Cargo Router Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Recursion

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galactic Cargo Router — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor