【Check 59】2024-04-23 - 46. 全排列

[larscheng]

46. 全排列

[larscheng]

思路

回溯

• 声明状态变量used来记录元素的使用状态，depth为当前收集深度
• 回溯终止条件：已收集到需要的数字，denpth==length时

  代码

class Solution { //回溯 // 声明状态变量used来记录元素的使用状态，depth为当前收集深度 // 回溯终止条件：已收集到需要的数字，denpth==length时 // O(nn!)/ O(nn!) public List<List> permute(int[] nums) { List<List> res = new ArrayList<>(); if (nums.length==0){ return res; } boolean[] used = new boolean[nums.length]; List path = new ArrayList<>();

    dfs(nums,nums.length,0,used,path,res);

    return res;

}

private void dfs(int[] nums, int length, int depth, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (depth==length){
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]){
            continue;
        }
        path.add(nums[i]);
        used[i] = true;

        dfs(nums,length,depth+1,used,path,res);

        used[i] = false;
        path.remove(path.size()-1);

    }

}

}

### 复杂度
- 时间复杂度：O(n*n!)
- 空间复杂度：O(n*n!)