全排列

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

 

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

code 

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums == null){return res;}
        ArrayList<Integer> path = new ArrayList<>();
        boolean [] isVisted = new boolean[nums.length];
        dfs(path,nums,isVisted);
        return res;
    }
    private void dfs(ArrayList path,int [] nums,boolean [] isVisted){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ;  i < nums.length ; i++){
            if(isVisted[i] == false){
                path.add(nums[i]);
                isVisted[i] = true;
                dfs(path,nums,isVisted);
                path.remove(path.size() - 1);
                isVisted[i] = false;
            }
        }
    }
}

PS

如果删除了 isVisited 来判断是否走过的话，则会出现例如

1,12,2的输出 即包括重复项

基于上一题的改造

改造

取其中的k项进行排序，

例如 [1,2,3,4] 可以排出[1,2,3]

代码

code 

class Solution {
    static List<List<Integer>> res = new ArrayList<>();
    public static List<List<Integer>> permute(int[] nums,int len) {
        if(nums == null){return res;}
        ArrayList<Integer> path = new ArrayList<>();
        boolean [] isVisted = new boolean[nums.length];
        dfs(path,nums,isVisted,len);
        return res;
    }
    private static void dfs(ArrayList path,int [] nums,boolean [] isVisted,int len){
        if(path.size() == len){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ;  i < nums.length ; i++){
            if(isVisted[i] == false){
                path.add(nums[i]);
                isVisted[i] = true;
                dfs(path,nums,isVisted,len);
                path.remove(path.size() - 1);
                isVisted[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int [] nums = new int[]{1,2,3,4};
        permute(nums,3).forEach(System.out::println);
    }
}

后续待更新

END

有问题请联系feinan6666@outlook.com

本文作者：
 文章标题：回溯/组合 整理
 本文地址：https://home.cnboy.top/90.html
 版权说明：若无注明，本文皆神码人の世界原创，转载请保留文章出处。
最后修改：2022 年 03 月 27 日 06 : 29 PM
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏