讨论/《深度优先搜索》 - 练习:全排列/
《深度优先搜索》 - 练习:全排列
共 2 个回复

Java版
递推和撤销的操作需要完全相反才是有效的撤销
详见!visited[i]时所做的操作

class Solution {
    List<List<Integer>> res;
    List<Integer> list;
    boolean[] visited;

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        list = new ArrayList<>();
        visited = new boolean[nums.length];

        dfs(nums, nums.length);
        return res;
    }

    void dfs(int[] nums, int n) {
        if (n == 0) res.add(new ArrayList<>(list));

        else for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                Integer integer = nums[i];
                list.add(integer);
                visited[i] = true;
                dfs(nums, n - 1);
                visited[i] = false;
                list.remove(integer);
            }
        }
    }
}
class Solution:
    def permute(self, ns: List[int]) -> List[List[int]]:
        # 回溯算法,复杂度较高,因为回溯算法就是暴力穷举,遍历整颗决策树是不可避免的
        res = []
        def dfs(pth, ns):
            if not ns:
                res.append(pth)
                return
            for i in range(len(ns)):
                dfs(pth + [ns[i]], ns[:i] + ns[i+1:])
        dfs([],ns)
        return res