题目求助|47 全排列2的一个疑问
1845
2021.10.25
2021.10.25
发布于 未知归属地

关于这道题,这个大佬的题解讲的很清楚了。但是我有个疑问,就是:
我理解这个题解每次调用dfs方法是循环测试同一个位置放不同的数进去,如果有重复就剪枝。但是,如果我的dfs方法是按照位置来循环呢?就是说每一层dfs要放的数已经固定,然后看数组中哪个位置能放得下,能放下就进入下一层dfs放下一个数。想问下这两种有何区别,我这种方法要怎么剪枝呢?
希望有大佬能解答下,谢谢

补充下,比如输入为[1,1',2],按照我的思路有下面的图(图有点不清,需要放大才好看清楚)
image.png

第一层dfs选择原数组中的第一个数:1. 循环遍历看哪个空的位置可以放得下。所以第一个数1有3个位置可以放心。
第二层dfs是在第一个1选了之后的基础上进行的,第二个1'可以放在另外两个空的位置上。所以就会有重复。如图所示颜色相同的是重复的。
第三层dfs将最后的一个数2放在唯一空的位置上。

就是说我这里每一层的dfs都是固定选好一个数的,然后将这个数遍历循环看能放在哪个空位置上。

导致了一个根本问题就是不知道用什么状态来表示重复,从而剪枝了

说变了就是两种dfs的思路:
第一种:每层dfs要放得位置是固定的,第一层dfs放得位置固定式0,然后选没用过的数轮流尝试放进去位置0
第二种:每层dfs要放得数是固定的,第一层dfs要放原数组中的第1个数,然后把这个数轮流尝试放到不同位置上

评论 (4)