Create Combinations

Return all combinations of exactly k of the given distinct integers (order within a combination follows the input; combinations are generated in index order).

createCombinations(nums, k)

Input format: nums | k. Output: each combination's values joined by spaces, combinations separated by ;.

Examples

nums=[1,2,3], k=2   // → "1 2;1 3;2 3"
nums=[1,2,3], k=1   // → "1;2;3"
nums=[1,2], k=0     // → ""   (one empty combination)

Walkthrough

Thinking it through

A combination of size k is a selection where order doesn't matter — {1,2} and {2,1} are the same. That's the key difference from permutations: avoid generating the same set more than once in different orders.

Why permutations-then-dedupe is the wrong instinct

Generating all orderings of every k-sized subset and filtering duplicates wastes enormous effort on arrangements you'll throw away. Better: prevent duplicates from ever being generated, by imposing a canonical order on how elements are chosen.

The trick: only look forward

Once you've chosen an element at some index, every later choice must come from a higher index. Enforce this with a "start" index tracking the earliest allowed position for the next pick:

If the current combination has k elements, record a copy.
Otherwise, try each candidate from the start index onward: append it, recurse with start one past it (so it and everything before can't be picked again), then remove it to try the next candidate.

Since every choice pulls from indices strictly greater than the previous one, any combination is discovered in exactly one order — increasing index order — so the same set of elements can never be produced twice.

Why this correctly enumerates all C(n,k) combinations

Every size-k subset has exactly one representation as an increasing index sequence. The search only considers increasing sequences and tries every one of length k — a perfect one-to-one correspondence with combinations. Nothing missed, nothing duplicated.

Why not build up from smaller combinations arithmetically

Pascal's-triangle-style recurrences give you how many combinations exist, not what they contain. Since the problem needs the actual combinations, walking the "which index next, always forward" decision tree is the natural approach — it constructs each combination as it goes.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.