Expert · Backtracking · 235 of 264
Choose k of n
Print every way to choose k different numbers from 1 to n, each in ascending order, in dictionary order. Do not use itertools.
Input: n and k on one line (n up to 10). Output: one combination per line.
Examples
Input
4 2
Output
1 2 1 3 1 4 2 3 2 4 3 4
Input
3 3
Output
1 2 3
Input
5 1
Output
1 2 3 4 5
One more test checks other inputs when you press Check.
Stuck? The idea behind backtracking
Build an answer one choice at a time; when a choice leads nowhere, undo it and try the next. Recursion keeps track of where you are.
Check as early as you can whether a partial answer can still work, so dead ends are left quickly.
def subsets(items, chosen=[]):
if not items:
print(chosen)
return
subsets(items[1:], chosen + [items[0]])
subsets(items[1:], chosen)
subsets([1, 2])Watch for: Changing a shared list without undoing the change afterwards leaves the next choice with the wrong start.