LeetCode(BackTracking)Permutations

Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：用递归回溯法解题时感觉有类似套路，最重要的是选择构建一个合适的递归函数，并且考虑好边界约束条件，以及回退时机和回退策略，还需好好体会这种思想。

代码如下：

public class Solution{
    public List<List<Integer>> permute(int [] arr){
        List<List<Integer>> res=new ArrayList<>();
        if(arr.length==0 || arr==null){
            return res;
        }
        backtracking(res,new ArrayList<Integer>(),arr);
        return res;
    }
    public void backtracking(List<List<Integer>> list,List<Integer> templist,int [] arr){
        if(templist.size()==arr.length){
            list.add(new ArrayList<>(templist));
            return;
        }else{
            for(int i=0;i<arr.length;i++){
                if(templist.contains(arr[i])){
                    continue;
                }
                templist.add(arr[i]);
                backtracking(list,templist,arr);
                templist.remove(templist.size()-1); //回退
            }
        }
        
    }
}