Simple Python Iterative Solution


  • 0
    E

    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


Log in to reply
 

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