# Simple Python Iterative Solution

• This code takes advantage of the implementation of Python itertools.combinations. You may see the reference here: https://docs.python.org/3/library/itertools.html#itertools.combinations

``````class Solution(object):
def combine(self, n, k):
res = []
comb = list(range(1, k + 1))
res.append(comb[:])

while True:
for i in reversed(range(k)):
if comb[i] != n - k + 1 + i:
break
else:
break

comb[i] += 1
for j in range(i + 1, k):
comb[j] = comb[j - 1] + 1

res.append(comb[:])

return res
``````

Each time in the loop, we try to find the next combination in the similar way to find next permutation. This is done in two steps:

1. Find the rightmost digit that needs to be updated and increase it by 1
2. Update the digits that come after the digit we get in step 1.

E.g. when n = 6, k = 4 and we're trying to find the combination that comes after `[1,2,5,6]`. `2` is the rightmost digit that can be updated, since `[5,6]` are already the largest possible combination for last two digits. Then we increase `2` by `1` and update the rest to get `[1,3,4,5]`.

The whole process will be:

``````[1,2,3,4]
[1,2,3,5] # Update from the 4th digit
[1,2,3,6] # Update from the 4th digit
[1,2,4,5] # Update from the 3rd digit
[1,2,4,6] # Update from the 4th digit
[1,2,5,6] # Update from the 3rd digit
[1,3,4,5] # Update from the 3rd digit
[1,3,4,6] # Update from the 4th digit
[1,3,5,6] # Update from the 3rd digit
[1,4,5,6] # Update from the 2nd digit
[2,3,4,5] # Update from the 1st digit
[2,3,4,6] # Update from the 4th digit
[2,3,5,6] # Update from the 3rd digit
[2,4,5,6] # Update from the 2nd digit
[3,4,5,6] # Update from the 1st digit
``````

Hope this helps

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.