Generate Bounded Combinations

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

You are given three distinct items and their respective maximum quantities. Additionally, an integer n is provided. Your task is to generate all possible sequences of length n where each element in the sequence is one of the three items, and the total number of times each item appears in the sequence does not exceed its given quantity. The sequences must be printed in lexicographical order based on the order of the items provided. Each sequence should be printed on a new line.

Examples:

Input: Items: A B C
Quantities: 2 1 1
n: 2

Output: AA
AB
AC
BA
BC
CA
CB

Explanation: The items A, B, C have maximum allowed counts 2, 1, 1. For n=2, all valid sequences where no item exceeds its count are listed in lex order based on item order A<B<C.

Input: Items: A B C
Quantities: 1 1 1
n: 2

Output: AB
AC
BA
BC
CA
CB

Explanation: With each item allowed at most once, all sequences of length 2 with distinct items are generated in lex order.

Input: Items: A B C
Quantities: 0 2 2
n: 2

Output: BB
BC
CB
CC

Explanation: Item A has quantity 0, so only B and C are used. Sequences are formed with at most 2 B and 2 C, in lex order B<C.

Constraints

Three distinct items are provided.
Quantities for each item are non-negative integers.
n is a positive integer.
1 ≤ n ≤ 5 (inferred for practical purposes)
0 ≤ quantity_i ≤ 5 for each i (inferred)

Editorial

Intuition:

We can use backtracking to generate all sequences of length n, at each step choosing an item that hasn't reached its maximum allowed quantity. By trying items in the given order at every position, we naturally generate sequences in lexicographical order.

Approach:

Initialize a counts array of size 3 with zeros to track how many times each item has been used.
Define a recursive function backtrack(pos, current) where pos is the current position (0-indexed) and current stores the sequence built so far.
If pos == n, print the current sequence and return.
Otherwise, iterate over each item index j from 0 to 2 (the given item order). If counts[j] < quantities[j], then: increment counts[j], append items[j] to current, recursively call backtrack(pos+1, current), then backtrack by decrementing counts[j] and removing the last character from current.
The recursion explores all valid sequences in lexicographical order because items are tried in the provided order at each step.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void backtrack(int pos, string& current, vector<int>& counts, const vector<char>& items, const vector<int>& quantities, int n) {
    if (pos == n) {
        cout << current << endl;
        return;
    }
    for (int j = 0; j < 3; ++j) {
        if (counts[j] < quantities[j]) {
            counts[j]++;
            current.push_back(items[j]);
            backtrack(pos + 1, current, counts, items, quantities, n);
            current.pop_back();
            counts[j]--;
        }
    }
}

void generateBoundedCombinations(vector<char> items, vector<int> quantities, int n) {
    vector<int> counts(3, 0);
    string current = "";
    backtrack(0, current, counts, items, quantities, n);
}
public class Solution {
    public static void backtrack(int pos, StringBuilder current, int[] counts, char[] items, int[] quantities, int n) {
        if (pos == n) {
            System.out.println(current.toString());
            return;
        }
        for (int j = 0; j < 3; j++) {
            if (counts[j] < quantities[j]) {
                counts[j]++;
                current.append(items[j]);
                backtrack(pos + 1, current, counts, items, quantities, n);
                current.deleteCharAt(current.length() - 1);
                counts[j]--;
            }
        }
    }

    public static void generateBoundedCombinations(char[] items, int[] quantities, int n) {
        int[] counts = new int[3];
        StringBuilder current = new StringBuilder();
        backtrack(0, current, counts, items, quantities, n);
    }
}
def generate_bounded_combinations(items, quantities, n):
    counts = [0, 0, 0]
    current = []

    def backtrack(pos):
        if pos == n:
            print(''.join(current))
            return
        for j in range(3):
            if counts[j] < quantities[j]:
                counts[j] += 1
                current.append(items[j])
                backtrack(pos + 1)
                current.pop()
                counts[j] -= 1

    backtrack(0)
function generateBoundedCombinations(items, quantities, n) {
    const counts = [0, 0, 0];
    const current = [];

    function backtrack(pos) {
        if (pos === n) {
            console.log(current.join(''));
            return;
        }
        for (let j = 0; j < 3; j++) {
            if (counts[j] < quantities[j]) {
                counts[j]++;
                current.push(items[j]);
                backtrack(pos + 1);
                current.pop();
                counts[j]--;
            }
        }
    }

    backtrack(0);
}

Complexity Analysis:

Time Complexity: O(3ⁿ) in the worst case (without quantity constraints), but with constraints it is bounded by the number of valid sequences S. Since each valid sequence requires O(n) work to build/print, total time is O(n * S). Given the constraints (n ≤ 5, quantities ≤ 5), S is very small (≤ 243).

Space Complexity: O(n) for the recursion stack and the current string/array being built. The counts array uses O(1) space.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories