Combinatorial Weight Distribution — Problem Statement & Solution Guide
Problem Description
Given a list of integers representing package weights and a target weight threshold, generate all distinct subsets of packages that sum up to the target weight, sorted in lexicographical order.
Examples
Input
[1, 2, 3, 4, 5] 5
Output
[[1, 4], [2, 3], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
Explanation: Step-by-step: First, we sort the input array. Then, we use a recursive function to generate all subsets of the array that sum up to the target weight. We use a helper function to check if a subset sums up to the target weight. We also use a set to store the subsets to avoid duplicates. Finally, we sort the subsets in lexicographical order and return them.
Input
[10, 20, 30, 40] 50
Output
[[10, 40], [20, 30], [10, 20, 30], [10, 20, 40], [10, 30, 40], [20, 30, 40], [10, 20, 30, 40]]
Explanation: Step-by-step: First, we sort the input array. Then, we use a recursive function to generate all subsets of the array that sum up to the target weight. We use a helper function to check if a subset sums up to the target weight. We also use a set to store the subsets to avoid duplicates. Finally, we sort the subsets in lexicographical order and return them.
Constraints
- 1 <= number of crates <= 20
- 1 <= weight of each crate <= 50
- 1 <= target capacity <= 100
Optimal Approach & Strategy
The optimized approach uses a recursive function with backtracking to efficiently generate combinations of crates that sum up to the target capacity, pruning branches that exceed the target capacity. This approach has a time complexity of O(n*target), where n is the number of crates.
Brute Force Approach
The brute-force approach involves generating all possible combinations of crates and checking if their total weight equals the target capacity. This approach has a time complexity of O(2^n) due to the recursive nature of combination generation.
Verified Code Solutions
function combinationSum(candidates, target) {
const result = [];
function backtrack(remain, comb, start) {
if (remain === 0) {
result.push([...comb].sort((a, b) => a - b));
return;
} else if (remain < 0) {
return;
}
for (let i = start; i < candidates.length; i++) {
backtrack(remain - candidates[i], [...comb, candidates[i]], i);
}
}
backtrack(target, [], 0);
const uniqueSubsets = [...new Set(result.map(JSON.stringify))].map(JSON.parse);
return uniqueSubsets.sort((a, b) => a.join(',') - b.join(''));
}import java.util.*;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(target, new ArrayList<>(), 0, candidates, result);
return result;
}
private void backtrack(int remain, List<Integer> comb, int start, int[] candidates, List<List<Integer>> result) {
if (remain == 0) {
result.add(new ArrayList<>(comb));
return;
} else if (remain < 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
comb.add(candidates[i]);
backtrack(remain - candidates[i], comb, i, candidates, result);
comb.remove(comb.size() - 1);
}
}
}def combinationSum(candidates, target):
def backtrack(remain, comb, start):
if remain == 0:
result.add(tuple(sorted(comb)))
return
elif remain < 0:
return
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
result = set()
backtrack(target, [], 0)
return [list(x) for x in result]function combinationSum(candidates, target) {
const result = [];
function backtrack(remain, comb, start) {
if (remain === 0) {
result.push([...comb].sort((a, b) => a - b));
return;
} else if (remain < 0) {
return;
}
for (let i = start; i < candidates.length; i++) {
backtrack(remain - candidates[i], [...comb, candidates[i]], i);
}
}
backtrack(target, [], 0);
const uniqueSubsets = [...new Set(result.map(JSON.stringify))].map(JSON.parse);
return uniqueSubsets.sort((a, b) => a.join(',') - b.join(''));
}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.