【数据结构与算法】【LeetCode】【dfs+回溯】77. 组合

class Solution:
    def combine(self,n,k):# n:int  k:int 返回值:List[List[]]
        res=list()
        if k<=0 or n<k:
            return res
        
        #  从1开始是题目的设定
        path =list() 
        self.dfs(n,k,1,path,res)
        return res
    def dfs(self,n,k,begin,path,res):
        
        # 递归终止条件：path长度等于k
        if len(path)==k:
            res.append(path[:])# 由于path递归结束为空，这里res添加的是地址，故这里拷贝一下
            return
        
        # 遍历所有可能的搜索起点
        for i in range(begin,n+1):
            # 向路径变量添加一个数
            path.append(i)
            print("递归前-->:",path)
            # 进行下一轮搜索，设置的搜索起点加1,因为组合数不允许出现重复的元素
            self.dfs(n,k,i+1,path,res)
            # 深度优先遍历有回去的过程，因此递归之前做了什么，递归之后需要形同的操作的逆向操作
            path.pop()
            print("递归后-->:",path)
           # print("i3:",i)
            #print("t3:",path)

a=Solution()
n=4
k=3
a.combine(n,k)

class Solution:
    def combine(self,n,k):# n:int  k:int 返回值:List[List[]]
        res=list()
        if k<=0 or n<k:
            return res
        
        #  从1开始是题目的设定
        path =list() 
        self.dfs(n,k,1,path,res)
        return res
    def dfs(self,n,k,begin,path,res):
        
        # 递归终止条件：path长度等于k
        if len(path)==k:
            res.append(path[:])# 由于path递归结束为空，这里res添加的是地址，故这里拷贝一下
            return
        
        # 遍历所有可能的搜索起点
        for i in range(begin,n-(k-len(path))+2):
            # 向路径变量添加一个数
            path.append(i)
            print("递归前-->:",path)
            # 进行下一轮搜索，设置的搜索起点加1,因为组合数不允许出现重复的元素
            self.dfs(n,k,i+1,path,res)
            # 深度优先遍历有回去的过程，因此递归之前做了什么，递归之后需要形同的操作的逆向操作
            path.pop()
            print("递归后-->:",path)

a=Solution()
n=4
k=3
a.combine(n,k)

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    
    pool = tuple(iterable)   # tuple([1,2])=(1,2) tuple("abc")=('a', 'b', 'c')
    n = len(pool)
    

    if r > n:
        return
    indices = list(range(r)) # list(range(2))=[0,1]
    yield tuple(pool[i] for i in indices) # yield生成器，下次从这里继续 
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

nums=[1,2,3]
list(combinations(nums,2))

import itertools

def combine(n,k):
    return list(itertools.combinations(range(1,n+1),k))

combine(4,2)