14.26 Find Index Combinations with Target Weight Sum

14.26.1 Problem Metadata

14.26.2 Description

Given an array of positive integers weights and a target capacity, return all unique combinations of indices whose corresponding weights sum to the capacity.

Key Requirements: - Each weight can be reused multiple times (unbounded) - Return combinations as lc-lists of indices (not weight values) - All combinations must be in non-decreasing index order - No duplicate combinations

Relationship to Similar Problems: This problem is a variant of Combination Sum (LeetCode 39) with a key difference: instead of returning the weight values themselves, you must return the indices of the weights used in each combination.

14.26.3 Examples

Example 1:

Input: weights = [2, 3, 6, 7], capacity = 7
Output: [[0, 0, 1], [3]]
Explanation:
- Index 3 has weight 7, so [3] is one combination (7 = 7)
- Using index 0 twice (weight 2) and index 1 once (weight 3): 2+2+3=7 → [0,0,1]
- No other combinations sum to 7

Example 2:

Input: weights = [2, 3, 5], capacity = 8
Output: [[0, 0, 0, 0], [0, 1, 1], [1, 2]]
Explanation:
- Four times index 0: 2+2+2+2=8 → [0,0,0,0]
- Index 0 once and index 1 twice: 2+3+3=8 → [0,1,1]
- Index 1 once and index 2 once: 3+5=8 → [1,2]

Example 3:

Input: weights = [3, 5], capacity = 8
Output: [[0, 1]]
Explanation:
- Only valid combination: 3+5=8 → [0,1]

14.26.4 Input Format

  • First line: integer weights_count (number of weights)
  • Next weights_count lines: each contains a single integer representing a weight
  • Final line: integer capacity (target sum)

Example:

6
8
4
5
3
9
6
15

This represents weights = [8, 4, 5, 3, 9, 6] and capacity = 15.

14.26.5 Output Format

Return a lc-list of lc-lists of integers, where each inner lc-list is a combination of indices in non-decreasing order whose corresponding weights sum exactly to capacity.

Print each combination on a separate line with space-separated indices.

Example:

0 0 0 0
0 1 1
1 2

14.26.6 Constraints

  • \(1 \le\) weights.length \(\le 30\)
  • \(1 \le\) weights[i] \(\le 1000\) for all \(0 \le i <\) weights.length
  • \(0 \le\) capacity \(\le 1000\)
  • All values are integers

14.26.7 Solution - Backtracking with Unbounded Knapsack

14.26.7.1 Walkthrough

This problem combines backtracking with unbounded knapsack to find all combinations of indices whose weights sum to a target capacity. The key insight is that we’re returning indices (not values) and each weight can be reused unlimited times.

2D Traversal Mental Model:

This problem uses the 2-dimensional traversal mental model of backtracking (see Pattern 1: Choose-Explore-Unchoose):

  • Outer dimension (recursion parameter): capacity / remaining target sum - controls how deep we recurse (from initial capacity down to 0)
  • Inner dimension (for-loop): Iterates through available weight indices from index to weights.size() - 1

The backtracking explores a conceptual 2D grid where: - Rows represent remaining capacity (from capacity down to 0) - Columns represent choices of which weight index to use next - Each cell represents a decision point: “Should I use weight at index i when I have capacity c remaining?”

Algorithm Strategy:

The solution uses the classic Choose-Explore-Unchoose backtracking pattern:

  1. Choose: Add the current index to the combination
  2. Explore: Recursively search for remaining combinations with reduced capacity
  3. Unchoose: Remove the last index to backtrack and try alternatives

Key Design Decisions:

  1. Why use index i (not i+1) in recursion?
    • We allow unbounded reuse of weights
    • Passing i allows the same index to be chosen again in the next recursive call
    • This is what makes it “unbounded” knapsack
  2. Why loop from index to weights.size()?
    • Maintains non-decreasing index order in results
    • Prevents duplicates like [0,1] and [1,0] being counted separately
    • The index parameter acts as a “start point” for valid choices
  3. Why must we copy current when adding to result?
    • current is mutated during backtracking
    • Without copying, all entries in result would reference the same (eventually empty) lc-list
    • new ArrayList<>(current) creates a snapshot of the current state

Visual Trace for weights = [2, 3, 5], capacity = 8:

backtrack([], index=0, cap=8)
│
├─ i=0: Choose index 0 → current=[0], cap=6
│  ├─ i=0: Choose 0 again → current=[0,0], cap=4
│  │  ├─ i=0: Choose 0 again → current=[0,0,0], cap=2
│  │  │  ├─ i=0: Choose 0 again → current=[0,0,0,0], cap=0 ✓ FOUND!
│  │  │  │  Unchoose → current=[0,0,0]
│  │  │  ├─ i=1: weight=3 > cap=2, skip
│  │  │  └─ i=2: weight=5 > cap=2, skip
│  │  │  Unchoose → current=[0,0]
│  │  ├─ i=1: Choose index 1 → current=[0,0,1], cap=1
│  │  │  └─ All weights too large
│  │  │  Unchoose → current=[0,0]
│  │  └─ i=2: weight=5 > cap=4, skip
│  │  Unchoose → current=[0]
│  ├─ i=1: Choose index 1 → current=[0,1], cap=3
│  │  ├─ i=1: Choose 1 again → current=[0,1,1], cap=0 ✓ FOUND!
│  │  │  Unchoose → current=[0,1]
│  │  └─ i=2: weight=5 > cap=3, skip
│  │  Unchoose → current=[0]
│  └─ i=2: weight=5 > cap=6, skip
│  Unchoose → current=[]
│
├─ i=1: Choose index 1 → current=[1], cap=5
│  ├─ i=1: Choose 1 again → current=[1,1], cap=2
│  │  └─ All weights too large
│  │  Unchoose → current=[1]
│  ├─ i=2: Choose index 2 → current=[1,2], cap=0 ✓ FOUND!
│  │  Unchoose → current=[1]
│  Unchoose → current=[]
│
└─ i=2: Choose index 2 → current=[2], cap=3
   └─ No valid combinations
   Unchoose → current=[]

Result: [[0,0,0,0], [0,1,1], [1,2]]

Why Unchoose Matters:

Without the unchoose step (current.remove(current.size() - 1)): - After finding [0,0,0,0], current would remain [0,0,0,0] - Trying to add index 1 would create [0,0,0,0,1] instead of [0,1] - You’d never explore paths starting with [1] or [2]

The unchoose step rewinds the state so each branch of the decision tree starts clean.

14.26.7.2 Analysis

Time Complexity: \(O(k \times C^{T/W_{min}})\) where: - \(T\) is the target capacity - \(W_{min}\) is the minimum weight - \(C\) is the number of distinct weights - \(k\) is the average length of each valid combination

Breaking down the complexity:

  1. Number of recursive calls: In the worst case, we explore all possible combinations of weights that sum to capacity.
    • Maximum depth of recursion tree: \(T/W_{min}\) (using smallest weight repeatedly)
    • Branching factor at each level: up to \(C\) choices (each weight index)
    • Total nodes in decision tree: \(O(C^{T/W_{min}})\)
  2. Work per recursive call: \(O(k)\) for copying current lc-list when adding to result
    • Only valid combinations trigger the copy operation
    • Most branches terminate early (capacity exceeded or no valid choices)
  3. Best case: \(O(C \times T)\) when few valid combinations exist
  4. Worst case: Exponential when many small weights create numerous combinations

Space Complexity: \(O(T/W_{min})\) for auxiliary storage (excluding output).

  1. Recursion stack depth: \(O(T/W_{min})\) - maximum depth occurs when using the smallest weight repeatedly
  2. Current combination lc-list: \(O(T/W_{min})\) - maximum length of a single combination
  3. Output lc-list: Not counted as auxiliary space (required by problem)

Total auxiliary space: \(O(T/W_{min})\) - dominated by recursion depth

Example Analysis: - For weights = [2, 3, 5], capacity = 8: - \(W_{min} = 2\), max depth = \(8/2 = 4\) - \(C = 3\) choices at each level - Maximum recursive calls: \(O(3^4) = 81\) nodes (worst case) - Actual combinations: 3 valid paths (much better than worst case)

14.26.7.3 Implementation Steps

Step 1: Initialize Result Collection - Create result lc-list to store all valid combinations - Initialize backtracking with empty current lc-list, starting index 0, and full capacity

Step 2: Define Backtracking Base Cases - Success case: When capacity == 0, we’ve found a valid combination - Critical: Must copy current using new ArrayList<>(current) - Add the copy to result and return - Pruning cases: Return early when: - index >= weights.size() (no more weights to explore) - capacity < 0 (exceeded target, invalid path)

Step 3: Explore All Valid Index Choices - Loop from i = index to weights.size() - 1: - Using i = index (not i = 0) ensures non-decreasing index order - This prevents duplicate combinations like [0,1] and [1,0]

Step 4: Apply Choose-Explore-Unchoose Pattern

For each valid weight that doesn’t exceed remaining capacity:

if (weight <= capacity) {
    // 1. CHOOSE: Add current index to combination
    current.add(i);

    // 2. EXPLORE: Recurse with same index (unbounded reuse)
    //    Pass 'i' (not 'i+1') to allow reusing this weight
    backtrack(weights, current, i, capacity - weight, result);

    // 3. UNCHOOSE: Remove last index to backtrack
    //    This restores state for trying alternative paths
    current.remove(current.size() - 1);
}

Key Points: - Choose: Tentatively add index i to explore this path - Explore: Recurse with i (not i+1) for unbounded reuse - Unchoose: Restore state by removing the last choice - Without this, current would grow indefinitely - This enables exploring alternative branches

Step 5: Return Result - After all recursive exploration completes, return the collected combinations - Each combination is in non-decreasing index order - No duplicates due to controlled iteration starting from index

14.26.7.4 Code - Java

class Result {

    /*
     * Complete the 'findCombinationsByWeightIndices' function below.
     *
     * The function is expected to return a 2D_INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY weights
     *  2. INTEGER capacity
     */

    public static List<List<Integer>> findCombinationsByWeightIndices(List<Integer> weights, int capacity) {
        List<List<Integer>> result = new ArrayList<>();
        
        backtrack(weights, new ArrayList<>(), 0, capacity, result);
        
        return result;
    }
    
    private static void backtrack(List<Integer> weights, List<Integer> current, int index, int capacity, List<List<Integer>> result) {
        // Base case: found valid combination
        if(capacity == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Base case: pruning - can't proceed if we've exhausted all indices
        if(index >= weights.size()) {
            return;
        }

        // Try all choices starting from 'index' to maintain non-decreasing order
        for(int i = index; i < weights.size(); i++) {
            int weight = weights.get(i);

            // Only add this index if weight doesn't exceed remaining capacity
            if(weight <= capacity) {
                // 1. CHOOSE: add current index
                current.add(i);

                // 2. EXPLORE: recurse with same index 'i' (allows unbounded reuse)
                backtrack(weights, current, i, capacity - weight, result);

                // 3. UNCHOOSE: remove last index to try other options
                current.remove(current.size() - 1);
            }
        }
    }

}