Permutations

Backtracking 类型的题目，类似的题目还有Subsets, Permutations, Combination Sum, Palindrome Partioning

相关题目结构：https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

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]
]

全排列问题

backtracking是往下递归 完了以后删除当前状态，

注意在往总的array里加的时候要深复制，不然会被全部删除

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