【算法刷题 | 回溯思想 07】4.18（全排列、全排列 ||）

11.全排列

11.1题目

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

• 示例一：

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

• 示例二：

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

11.2解法：回溯

11.2.1回溯思路

（1）函数返回值以及参数

private void backing(int[] nums)

（2）函数返回值

if(paths.size()==nums.length){
res.add(new ArrayList(paths));
    return;
}

（3）遍历过程

for(int i=0;i<nums.length;i++){
if(isUsed[i]==true){
        //该元素已经用过了
        continue;
    }
    isUsed[i]==true;
    paths.add(nums[i);
    backing(nums);
                   
    //回溯
    isUsed[i]=false;
    paths.remove(paths.size()-1);
}

11.2.2代码实现

List<List<Integer>> res=new ArrayList<>();
    List<Integer> paths=new ArrayList<>();
    boolean[] isUsed;

    public List<List<Integer>> permute(int[] nums) {
        isUsed=new boolean[nums.length];
        Arrays.fill(isUsed,false);
        backing(nums);
        return res;
    }

    private void backing(int[] nums){
        if(paths.size()==nums.length){
        res.add(new ArrayList(paths));
            return;
        }
        for(int i=0;i<nums.length;i++){
        if(isUsed[i]==true){
                //该元素已经用过了
                continue;
            }
            isUsed[i]=true;
            paths.add(nums[i]);
            backing(nums);

            //回溯
            isUsed[i]=false;
            paths.remove(paths.size()-1);
        }
    }

12.全排列 ||

12.1题目

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

• 示例一：

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

• 示例二：

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

12.2解法：回溯

12.2.1回溯思路

12.2.3代码实现

List<List<Integer>> res=new ArrayList<>();
    List<Integer> paths=new ArrayList<>();
    boolean[] isUsed;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        isUsed=new boolean[nums.length];
        Arrays.fill(isUsed,false);
        backing(nums);
        return res;
    }

    private void backing(int[] nums){
        if(paths.size()==nums.length){
        res.add(new ArrayList(paths));
            return;
        }
        for(int i=0;i<nums.length;i++){
        if(isUsed[i]==true){
                //同一树枝上，该元素已经用过了
                continue;
            }
            if(i>0 && nums[i]==nums[i-1] && isUsed[i-1]==false){
                //同一树层上，该元素已经用过了
                continue;
            }
            isUsed[i]=true;
            paths.add(nums[i]);
            backing(nums);

            //回溯
            isUsed[i]=false;
            paths.remove(paths.size()-1);
        }
    }

原文地址：https://blog.csdn.net/weixin_61440595/article/details/137915124

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！