LeetCode----Combinations

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

分析:
組み合わせの問題.遡及法を用いて解決するのに適しており,python下地itertoolsにもcombinations関数が提供されている.
遡及法:

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ans = []
        self.dfs(n, k, 1, [], ans)
        return ans

    def dfs(self, n, k, start, lst, ans):
        if not k:
            ans.append(lst)
            return
        for i in range(start, n + 1):
            self.dfs(n, k - 1, i + 1, lst + [i], ans)

itertools.combinations:

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        from itertools import combinations
        return [list(c) for c in combinations(range(1, n+1), k)]

遡及法2:

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ans = []
        stack = []
        x = 1
        while True:
            l = len(stack)
            print stack, x, 2 + l
            if l == k:
                ans.append(stack[:])
            if l == k or x > n - k + l + 1:
                if not stack:
                    return ans
                x = stack.pop() + 1
            else:
                stack.append(x)
                x += 1

遡及法2はLeetCodeのDiscussに由来する.
コード解釈:Combinations is typicalアプリケーションfor backtracking.Two conditions for backtrack:(1)the stack length is already k(2)the current value is too large for the rest slots to fit in since we are using ascending order to make sure the uniqueness of each combination.
Combinationsは典型的な遡及法を適用する問題型である.このコードは、(1)スタックの長さがkに達したとき、(1)スタックの長さがkに達したとき、(2)現在の値が大きすぎてスタックに入れられない(昇順に要素を追加するため、毎回発生する解が繰り返されないことを確保できる).