leetcode46-全排列

原题

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1] ]

解法

思想

做这道题的时候我才发现我做这类回溯算法的题还是蛮少的,对集合的深克隆api不是很熟悉。主要是深克隆的蛮麻烦 -。-||

思想就是回溯啦,可以用一个数组记录使用过了的元素。

代码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int[] globalNums;
    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length];
        globalNums = nums;
        List<Integer> list = new ArrayList<>();
        trackback(list,used,0);
        return ans;
    }
    public void trackback(List<Integer> list,int[] used,int usedCount){
        if(usedCount==globalNums.length){
            ans.add(list);
        }
        for(int i = 0;i<globalNums.length;i++){
            if(used[i]==0){
                List<Integer> copy = new ArrayList<>(list);
                copy.add(globalNums[i]);
                int[] usedCopy = Arrays.copyOf(used,used.length);
                usedCopy[i] = 1;
                trackback(copy,usedCopy,usedCount+1);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode46-%e5%85%a8%e6%8e%92%e5%88%97/

发表回复

登录后才能评论