力扣第46题-全排列

题目
题目链接

题解

import java.util.ArrayList;
import java.util.Stack;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>(0);
        }
        List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> node = new Stack<>();
        dfs(node, res, nums, new boolean[nums.length]);
        return res;
    }

    /**
     * 深度优先遍历，回溯
     * @param node 树的每个节点
     * @param res 结果集
     * @param nums 传入参数
     * @param used 状态
     */
    private void dfs(Stack<Integer> node, List<List<Integer>> res, int[] nums, boolean[] used) {
        // 递归树达到最深层，添加结果集并结束
        if (node.size() == nums.length) {
            List<Integer> currRes = new ArrayList<>(node);
            res.add(currRes);
            return;
        }
        // 继续递归
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (used[i]) {
                continue;
            }
            // 推入节点
            node.push(nums[i]);
            // 变更状态
            used[i] = true;
            // 递归
            dfs(node, res, nums, used);
            // 弹出节点
            node.pop();
            // 回更状态
            used[i] = false;
        }
    }
}