leetcode 77 组合

通过回溯加判断条件剪枝，如果加入路径的值不能比前一个值小。

组合问题通常需要通过某种顺序展开

组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        def dfs(i,n,k,path,result):
            if i==k:
                result.append(path[:])
                return 
            for j in range(1,n+1):
                if j in path:continue
                if len(path)!=0 and j<path[-1]:continue

                path.append(j)
                dfs(i+1,n,k,path,result)
                path.pop()

        result=[]
        dfs(0,n,k,[],result)
        return result

递归，每次会新建一个数组空间，防止分支之间会相互扰乱。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        def dfs(i,n,k,path,result):
            if i==k:
                result.append(path)
                return 
            for j in range(1,n+1):
                if j in path:continue
                if len(path)!=0 and j<path[-1]:continue

                #path.append(j)
                dfs(i+1,n,k,path+[j],result)
                #path.pop()

        result=[]
        dfs(0,n,k,[],result)
        return result

每次深搜后以当前元素为起点继续搜索，剪枝条件为是否剩下的元素还可以形成k大小的数组。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        def dfs(i,n,k,path,result):
            if len(path)==k:
                result.append(path[:])
                return 
            for j in range(i,n+1):

                #if j in path:continue
                if n-j+1<k-len(path):continue#判断剩下元素是否够组成k大小的序列（数组）

                path.append(j)
                dfs(j+1,n,k,path,result)
                path.pop()

        result=[]
        dfs(1,n,k,[],result)
        return result