题解 | #没有重复项数字的全排列，递归回溯#

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>() ;
        help(num , 0 , new ArrayList<>() , res) ;
        return res ;
    }
    /*
    得到arr[start]及其之后所有元素的全排列，并将结果保存到res中
    其中tmp保存的是当前arr[start]的值
    */
    public void  help(int []arr , int start , ArrayList<Integer> tmp,ArrayList<ArrayList<Integer>> res) {
        if(start == arr.length) {
            ArrayList<Integer> r = new ArrayList<>(tmp) ;
            res.add(r) ;
            return ;
        }
        for(int j = start ; j < arr.length ; j ++) {//这个位置之后的元素，都可能出现在start位置
            swap(arr , start , j) ;//和j位置元素交换
            tmp.add(arr[start]) ;//保存新的arr[start]
            help(arr , start + 1 , tmp , res) ;//求start位置之后的元素的全排列
            swap(arr , start , j) ;//递归返回后，恢复现场
            tmp.remove(tmp.size()-1) ;//移除当前元素，恢复现场
        }            
        
    }
    //交换元素
    public void swap(int num[] , int i , int j) {
        int t = num[i] ;
        num[i] = num[j] ;
        num[j] = t ;
    }
}