Combinatorial Weight Distribution — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Recursion and solve the Combinatorial Weight Distribution problem optimally.
O(2^n)O(n)Problem Description
Given an integer array nums and an integer target, enumerate every unique subset of nums whose elements sum exactly to target. Each subset must be presented in non‑decreasing order, and the collection of subsets must be sorted lexicographically (i.e., compare the first differing element of two subsets). The input may contain duplicate values, but subsets that are identical as multisets should appear only once in the output. Return the list of qualifying subsets; if none exist, return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Combinatorial Weight Distribution"
WHY DOES IT MATTER?
Subset‑sum with uniqueness constraints appears in resource allocation, budgeting, and combinatorial optimization tasks where duplicate items exist. Mastering this pattern teaches you how to systematically explore exponential spaces while eliminating redundancy, a skill that scales to many real‑world problems.
OPTIMIZATION CHALLENGE
The breakthrough is to sort the input and skip duplicate values during recursion, turning a potentially massive duplicate‑heavy search into a clean enumeration of unique multisets, while early sum‑based pruning cuts off hopeless branches.
REAL-WORLD CONNECTION
Think of a distributed storage system that must select a set of servers whose combined capacity meets a request size. Servers may have identical capacities, and you need to list all distinct server groups without repeats—exactly the same reasoning as the weighted subset enumeration.
When coding this in an interview, first sort the array, then write a clean backtrack helper that takes (index, currentSum, path). Inside the loop, check for duplicates with if i > start && nums[i] == nums[i-1] continue; and prune when currentSum + nums[i] > target.
COMPLEXITY AT A GLANCE
O(2^n)O(n)Core Theory — Why This Approach?
The combinatorial weight distribution problem is a classic variant of the subset‑sum problem. At its heart lies a recursive exploration of the decision tree: for each element we either include it in the current subset or skip it, building up a candidate list whose sum we compare against the target. Because the output must contain each unique subset in non‑decreasing order and the collection sorted lexicographically, we first sort the input array. This ordering lets us generate subsets in a deterministic order and provides a simple way to skip duplicates – if the current element is the same as the previous one and the previous was not chosen, we can safely ignore the current branch without losing any unique combination.
A naïve solution would generate all 2^n possible subsets, compute their sums, and then filter out those that match the target while deduplicating afterwards. This approach quickly becomes infeasible as n grows: the exponential blow‑up dominates runtime, and handling duplicates after the fact requires expensive set operations or sorting of each subset. Moreover, without early pruning the algorithm wastes time exploring branches that already exceed the target, leading to unnecessary work.
The optimal paradigm combines backtracking with two key optimizations. First, sorting the array enables early termination: if the running sum plus the smallest remaining element exceeds the target, we can backtrack immediately. Second, by skipping over consecutive duplicate values during the recursion, we guarantee that each multiset appears only once, satisfying the uniqueness requirement without extra post‑processing. The resulting algorithm runs in O(2^n) worst‑case time (the same as enumerating all subsets) but often performs far better in practice due to pruning, and it uses O(n) auxiliary space for the recursion stack and the current path.
Interview Questions on This Problem
Q1Global Product Company: How would you design an algorithm to return all unique subsets that sum to a target while preserving lexicographic order, and what is its time complexity?
Sort the input, then use a depth‑first backtracking routine that at each index decides to include or skip the element, skipping duplicates when the previous identical element was not taken. This generates subsets in sorted order; the worst‑case time is O(2^n) with O(n) extra space.
Q2FinTech Platform: In a portfolio‑rebalancing tool you need to find every combination of asset weights that hits a target exposure, and the weight list may contain many duplicate values. How would you adapt the subset‑sum backtracking to handle this efficiently?
After sorting the weight list, the backtracking step skips over consecutive duplicates unless the previous duplicate was part of the current path. This ensures each multiset of weights is produced once, avoiding exponential blow‑up from duplicate branches while still exploring all valid combinations.
Q3High‑Growth Startup: When n can be up to 30 and target up to 10^9, what pruning techniques can you add to the recursion to keep runtime acceptable?
Implement two prunings: (1) stop exploring a branch when the running sum exceeds the target, and (2) if the running sum plus the sum of all remaining smallest elements is still less than the target, backtrack because you cannot reach the target any more. These cuts dramatically reduce the explored search space.
Examples
Input
nums = [2,3,5,6,8], target = 10
Output
[[2,3,5],[2,8]]
Explanation: All combinations that sum to 10 are examined. 2+3+5=10 yields [2,3,5]; 2+8=10 yields [2,8]. No other selection of numbers reaches the target. After sorting each subset and ordering them lexicographically, [2,3,5] precedes [2,8].
Input
nums = [1,1,2,3], target = 4
Output
[[1,1,2],[1,3]]
Explanation: Possible sums: 1+1+2=4 gives [1,1,2]; 1+3=4 gives [1,3]. The duplicate 1 values are treated as distinct positions, but the resulting subsets are identical as multisets, so each appears only once. Lexicographic order places [1,1,2] before [1,3].
Input
nums = [4,5,6,7], target = 12
Output
[[5,7]]
Explanation: Scanning all subsets, only 5+7 equals 12, producing the subset [5,7]. No other combination reaches the target, so the final list contains a single element.
Constraints
- 1 <= nums.length <= 20
- 1 <= nums[i] <= 50
- 1 <= target <= 500
- All numbers are integers
- Subsets must be returned in lexicographic order
Optimal Approach & Strategy
Use sorted input and backtracking with duplicate‑skipping and early sum pruning to generate only valid, unique subsets directly in the required order.
Brute Force Approach
Generate every possible subset (2^n of them), compute each subset's sum, and keep those that equal the target, then deduplicate and sort. This method is exponential and wastes time on irrelevant branches.
Code Solutions
/**
* @param {number[]} nums - Input array of integers (may contain duplicates)
* @param {number} target - Target sum
* @return {number[][]} - A 2D array representing all unique subsets that sum to target.
*/
function combinationSum(nums, target) {
nums.sort((a, b) => a - b);
const uniqueSubsets = new Set();
const result = [];
const current = [];
function backtrack(start, remaining) {
if (remaining === 0) {
const key = current.join(',');
if (!uniqueSubsets.has(key)) {
uniqueSubsets.add(key);
result.push([...current]);
}
return;
}
if (remaining < 0) {
return;
}
for (let i = start; i < nums.length; i++) {
// Skip duplicates at the same level
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
current.push(nums[i]);
backtrack(i + 1, remaining - nums[i]);
current.pop();
}
}
backtrack(0, target);
// Sort lexicographically
result.sort((a, b) => {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
if (a[i] !== b[i]) {
return a[i] - b[i];
}
}
return a.length - b.length;
});
return result;
}
// Example usage
const nums = [2, 3, 5, 6, 8];
const target = 10;
const result = combinationSum(nums, target);
console.log(JSON.stringify(result));#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
set<vector<int>> uniqueSubsets;
vector<int> current;
function<void(int, int)> backtrack = [&](int start, int remaining) {
if (remaining == 0) {
uniqueSubsets.insert(current);
return;
}
if (remaining < 0) {
return;
}
for (int i = start; i < nums.size(); ++i) {
// Skip duplicates at the same level
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
current.push_back(nums[i]);
backtrack(i + 1, remaining - nums[i]);
current.pop_back();
}
};
backtrack(0, target);
vector<vector<int>> result(uniqueSubsets.begin(), uniqueSubsets.end());
return result;
}
int main() {
vector<int> nums = {2, 3, 5, 6, 8};
int target = 10;
vector<vector<int>> result = combinationSum(nums, target);
for (const auto& subset : result) {
cout << "[";
for (size_t i = 0; i < subset.size(); ++i) {
cout << subset[i];
if (i < subset.size() - 1) cout << ",";
}
cout << "] ";
}
cout << endl;
return 0;
}import java.util.*;
public class Solution {
/**
* Returns all unique subsets of nums that sum to target.
*/
public List<List<Integer>> combinationSum(int[] nums, int target) {
Arrays.sort(nums);
Set<List<Integer>> uniqueSubsets = new HashSet<>();
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
backtrack(nums, target, 0, 0, current, uniqueSubsets, result);
// Sort lexicographically
result.sort((a, b) -> {
for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
if (a.get(i) != b.get(i)) {
return a.get(i) - b.get(i);
}
}
return a.size() - b.size();
});
return result;
}
private void backtrack(int[] nums, int target, int start, int currentSum,
List<Integer> current, Set<List<Integer>> uniqueSubsets,
List<List<Integer>> result) {
if (currentSum == target) {
List<Integer> copy = new ArrayList<>(current);
if (uniqueSubsets.add(copy)) {
result.add(copy);
}
return;
}
if (currentSum > target) {
return;
}
for (int i = start; i < nums.length; i++) {
// Skip duplicates at the same level
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
current.add(nums[i]);
backtrack(nums, target, i + 1, currentSum + nums[i], current, uniqueSubsets, result);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
int[] nums = {2, 3, 5, 6, 8};
int target = 10;
Solution solution = new Solution();
List<List<Integer>> result = solution.combinationSum(nums, target);
for (List<Integer> subset : result) {
System.out.print("[");
for (int i = 0; i < subset.size(); i++) {
System.out.print(subset.get(i));
if (i < subset.size() - 1) System.out.print(",");
}
System.out.print("] ");
}
System.out.println();
}
}from typing import List
def combinationSum(nums: List[int], target: int) -> List[List[int]]:
"""
Returns all unique subsets of nums that sum to target.
"""
nums.sort()
unique_subsets = set()
result = []
current = []
def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
key = tuple(current)
if key not in unique_subsets:
unique_subsets.add(key)
result.append(list(current))
return
if remaining < 0:
return
for i in range(start, len(nums)):
# Skip duplicates at the same level
if i > start and nums[i] == nums[i - 1]:
continue
current.append(nums[i])
backtrack(i + 1, remaining - nums[i])
current.pop()
backtrack(0, target)
# Sort lexicographically
result.sort()
return result
# Example usage
if __name__ == "__main__":
nums = [2, 3, 5, 6, 8]
target = 10
result = combinationSum(nums, target)
print(result)/**
* @param {number[]} nums - Input array of integers (may contain duplicates)
* @param {number} target - Target sum
* @return {number[][]} - A 2D array representing all unique subsets that sum to target.
*/
function combinationSum(nums, target) {
nums.sort((a, b) => a - b);
const uniqueSubsets = new Set();
const result = [];
const current = [];
function backtrack(start, remaining) {
if (remaining === 0) {
const key = current.join(',');
if (!uniqueSubsets.has(key)) {
uniqueSubsets.add(key);
result.push([...current]);
}
return;
}
if (remaining < 0) {
return;
}
for (let i = start; i < nums.length; i++) {
// Skip duplicates at the same level
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
current.push(nums[i]);
backtrack(i + 1, remaining - nums[i]);
current.pop();
}
}
backtrack(0, target);
// Sort lexicographically
result.sort((a, b) => {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
if (a[i] !== b[i]) {
return a[i] - b[i];
}
}
return a.length - b.length;
});
return result;
}
// Example usage
const nums = [2, 3, 5, 6, 8];
const target = 10;
const result = combinationSum(nums, target);
console.log(JSON.stringify(result));Asked in Top Tech Interviews
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.