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] ]
规律：类似插入排序，每个数都有多个可插入的位置。
递归的时候：循环插入的位置。递归结束条件：插入到最后一个数。
class Solution { public List<List<Integer>> permute(int[] nums) { List<Integer> ans = new ArrayList<Integer>(); if(nums.length == 0) return ret; ans.add(nums[0]); insertNum(nums, 1, ans); return ret; } public void insertNum(int[] nums, int index, List<Integer> ans){ if(index == nums.length) { List<Integer> new_ans = new ArrayList<Integer>(ans); ret.add(new_ans); return; } //insert in the back ans.add(nums[index]); insertNum(nums, index+1, ans); ans.remove(ans.size()-1); //recover for(int j = 0; j < ans.size(); j++){ //iterate all possible insert position ans.add(j,nums[index]); insertNum(nums, index+1, ans); ans.remove(j); //recover } } private List<List<Integer>> ret = new ArrayList<List<Integer>>(); }
原文：https://www.cnblogs.com/qionglouyuyu/p/10819713.html