剑指offer—全排列 解答

剑指offer—全排列

题目描述

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

示例:

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

思路—递归+回溯

我们要找到所有的全排列,就需要对数组元素进行递归交换,但是每一次交换了递归后还要交换回去,不然会有重复的全排列

  • 每次循环固定一位,对剩下的进行交换递归
  • 交换的时候,依次跟自己和自己后面的每一位进行交换(所以需要交换回去,也叫回溯)
  • 当递归到固定了前n-1个元素,只有最后一个元素的时候,就把这个集合添加到list结果集合中
  • 因为要返回List<List<Integer>>类型集合,所以要先把所有的数组元素添加到一个集合中,递归交换这个集合

6

代码

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length==0) return list;
        ArrayList<Integer> l = new ArrayList<>();
        for (int num : nums) l.add(num);
        digui(0,l);
        return list;
    }
    public void digui(int index,ArrayList<Integer> l){
        if(index == l.size()-1) {list.add(new ArrayList<Integer>(l));return;}
        else{
            for(int i=index;i<l.size();i++){
                swap(l,index,i);
                digui(index+1,l);
                swap(l,index,i);
            }
        }
    }
    public void swap(List<Integer> l,int a,int b){
        int temp = l.get(a);
        l.set(a,l.get(b));
        l.set(b,temp);
    }
}