请教backtracking, dfs, bfs，dp具体算法实现

这个帖子主要是从具体代码角度来看这几种算法，不是数学角度，本人CS小白，有几个问题想问一下大家：先简单确认一下概念，dfs就是深度优先BST里直接一条叉搜索到头然后一点一点往回，backtracking就是dfs里加一些constraint，不满足直接prune branches然后break，bfs就是广度优先BST里先看最顶部node之下能分叉到哪几种选择，然后看每个node都有哪几种选择，一点一点往下延伸，dfs，backtracking，bfs一般是罗列所有可能性，而dp主要是用于优化，大部分题目中都是create一个true false dp array，遍历满足条件就true不然就是default false，return dp[-1]一般就是结果。我其实主要想问的是backtracking和dfs的具体区别，我看网上有人说backtracking是dfs的一种，有人说dfs是backtracking的一种，所以我很混乱。

这样，我拿一道比较经典的recursive题目来举个例子：
比如给定一个array = [1,2,3]
要求return所有subset的可能性：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 不限定先后这样
我想出了三种解法，用python简单写一下，都是按照我认为的文字概念写出来的哈：
1. 我认为的bfs:         
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def bfs(n, cur_index, cur_list):


            if n == len(cur_list):
                ans.append(cur_list.copy())

            for i in range(cur_index,len(nums)):
                cur_list.append(nums)
                bfs(n,i+1,cur_list)
                cur_list.pop()
        for i in range(len(nums)+1):
            bfs(i,0,[])
        return ans

由于我前面加了一个限制n 就是每次循环中只append和i保持一样长度的array，这样得到的结果就是[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]，然后遍历到头就pop()，不知道这算bfs还是dfs，我有个朋友说这个也是dfs。。。但我觉得这是bfs吧，return结果先把len = 1的subset列进去了，然后是len = 2，最后是3。。。所以这是dfs还是bfs请大神解答下。

2. 我认为真正的dfs解法：
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans=[]
        def dfs(l,cur):
            ans.append(l)
            for i in range(cur, len(nums)):
                temp = l.copy()
                temp.append(nums)
                dfs(temp,i+1)
        dfs([],0)
        return ans
每次都在遍历中通过新定义一个temporary array来进行接下来的递归，这样return出来的结果是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]，每次都是把最长的可能性append之后才回到之前一步的原始状态的array “l”。

3. 我认为的backtracking：
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtracking(cur,s):

            ans.append(cur.copy())
            for i in range(s, len(nums)):
                cur.append(nums)
                backtracking(cur, i+1)
                cur.pop()

        backtracking([],0)
        return ans
整体思路和上面的dfs差不多，但是这个相当于直接用方法2中的l不新定义temporary list来直接进行每一次递归，但是递归至最深后通过pop()来prune tree回归到之前状态的未append新数字的current_list，这样return出来的结果也是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]，和dfs得到的subarray的顺序是一样的。
请问我这么理解的对吗？单纯想求大佬从代码角度来解释一下定义，谢谢！

1 本身的确就是个 dfs，因为你还没有 breath first 就往下走了。。

参考 https://www.techiedelight.com/breadth-first-search/ 有 iterative 和 recursive 的 bfs

阵雨 发表于 2022-8-10 12:31
1 本身的确就是个 dfs，因为你还没有 breath first 就往下走了。。

参考 https://www.techiedelight.com ...

另外请问一下2和3里dfs和backtracking有区别吗？我上面的理解对吗？就是backtracking一般会有pop()或者del 之类的，而普通dfs不需要通过prune吗？还是说backtracking和dfs就是包含和被包含的关系呢？🤔

nanoice 发表于 2022-8-10 12:48
另外请问一下2和3里dfs和backtracking有区别吗？我上面的理解对吗？就是backtracking一般会有pop()或者de ...

不用太纠结。。一般普遍认为 backtracking 是 dfs 的一个特例而已。。

pop 和 del 不一定必须，因为可以通过 idx+1, cur+nums[i] 这种来实现。。。

一般 backtrack 就是 dfs 加上一些返回条件然后继续测试其他。。所以可以认为是 dfs 的一个特例