77组合(易懂)!!!读完这个问题,了解回溯和递归,最,看,完此题,理解

发表时间:2020-09-14

题目

给定一个数组n和一个整数k,利用n内的数找出所有的排列数组,规定每个数组内不能有相同的元素,并且数组内的元素个数为k。举例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

讲解

首先,拿到这道题目,追根溯源,啥也没想,直接暴力是最好解决的,一开始我压根没去想什么回溯递归剪枝等等复杂的概念,那么我们开始暴力吧。。。。

步骤一:
① 假设题目所给样例,n,k = 4, 2 那么我们有:

        nums = [i for i in range(1, n+1)]
        ans = []

        for i, item1 in enumerate(nums[0:]): # nums中的第一个数在每一层会变(也就是index)
            for j, item2 in enumerate(nums[i+1:]): 
                print([item1, item2]) # 这个输出里面的参数会变(随着k),也就是tmp

也就是说,k为多少,层数就为多少,我们直接写循环没办法控制层数,我们不得不用递归,因此我们必须找出那些会变的变量,这是关键。

② 我们知道,当取了一个数,之后,第二个数我们只能取它后面的数,也就是进行这个数后面的循环,同理第三个数只能取第二个数后面的某个数(即进行第二次循环)
只有这样做,我们才能实现组合不重复,并且里面的元素也不重复使用。

③ 那么什么变量会变呢?首先是index,它是第i(i=[1,2,…,k])次循环指向的数,想想看,我们只要指定了第i轮循环的index,那么后面的循环就确定了。

④ 其次是tmp,它是存放我们上一步循环到的数的,不能总放的去,放到k我们就放在我们最后要输出的答案列表ans里面。

⑤ 除了上面两步之外,我们没有其他的变量会变了。因为index到了最后一个元素也就得出了最后的ans列表。

代码

手动代码

n, k = 4, 3
nums = [i for i in range(1, n+1)]
ans = [] # 存输出

def traceback(index, tmp): # 这里放所谓的两个会变化的量

    if len(tmp) == k: # 这次探索有k这么长了,我就停止,输出到ans答案列表中
        ans.append(tmp[:]) # 软复制,如果直接写tmp,由于tmp是个列表,只能传引用,那么tmp会被反复更改。。。。
        return

    for i in range(index, n): # 这就是在进行第一轮
        tmp.append(nums[i]) # 第一个数进去
        traceback(i+1, tmp) # 我们把数组缩小一点,再做上面的第三步,也就是反复做相同的事情。但是我们讨论过了,index和tmp是肯定会变的。
        tmp.pop() # 这是个循环,从循环一开始我进去一个数,到了最后肯定要把这个数扔掉才能进行下一次循环,从而塞进下一个数去,如果不pop,那么tmp里面就只是一个连续的数列了。。。。
    

if __name__ == '__main__':
    traceback(0, []) # 初始化,index从位置0开始,tmp一开始也是空的
    
    print(ans)

调包侠:

注:可以区分一下itertools中的permutations、collections和combinations的区别!

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
    	import itertools
        return(list(itertools.combinations(range(1,n+1),k)))

总结

① 真正理解一道题目不要一开始去套模板,要去思考我如何让计算机傻瓜式的做同一件事情,我们只负责改变变量。
② 所谓回溯递归真正难写的原因并不是我们搞不懂递归和回溯的定义和概念是什么,而是我们没有办法找到每一次做重复事情的时候(递归)所改变的变量是什么,这些变量的改变肯定是遵循一定的规律的,也就是说,不可能是每一轮随机变化的。
③ 同理,动态规划DP也是如此,关键的难点在于我们要找到状态转移的那个方程,也就是变量变化的规律

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free