Permutation Summary

Method:
Iteration and recursion.

Like the code in this post, they are from me and easier for me to understand and memorize.
http://mashijie.blogspot.ca/2015/07/string-permutation.html

Below are newer posts and borrowed from the Net. I just could not believe that I would have totally forgotten what I come up a year earlier.

In iteration, it loops through the queue to continuously build it up, An example can be found here.
http://mashijie.blogspot.ca/search?q=subsets

In recursion, it tries to work the resolved with unused elements. An example can be found here:
http://mashijie.blogspot.ca/2016/07/permutations.html

SubSets, also a basic method of permutation

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
] 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution { public List<List<Integer>> subsets(int[] nums) { if (nums == null){ return null; } //not necessary // Arrays.sort(nums); //this is also basic method of permutation List<List<Integer>> result = new ArrayList<List<Integer>>(); for (int i = 0; i < nums.length; i++) { //new list is created based on existing list, by adding one more new number List<List<Integer>> newList = new ArrayList<List<Integer>>(); //build the newlist from existing list, existing lists are still there for (List<Integer> a : result) { newList.add(new ArrayList<Integer>(a)); } //add new number to existing sets for (List<Integer> a : newList) { a.add(nums[i]); } //in a loop of each element, creating single element set List<Integer> single = new ArrayList<Integer>(); single.add(nums[i]); newList.add(single); //adding new lists to result, when result is processed in next loop, more content will be added the ///same way result.addAll(newList); } //add empty set. it will be wrong if adding empty set the first, because it will be permunated with //other new elements result.add(new ArrayList<Integer>()); return result; } }

Permutations

Given a list of numbers, return all possible permutations.

Algorithm:
take one number, permute it with permutation of rest of numbers, so recursive is a natural call.
length here is same length as number of numbers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { /** * @param nums: A list of integers. * @return: A list of permutations. */ public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) { // write your code here ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if(nums==null)return result; ArrayList<Integer> pList = new ArrayList<Integer>(); permuteRest(nums,pList,result); return result; }  //pList: element path. I am basically building up the pList with recursive calls  void permuteRest(ArrayList<Integer> nums,ArrayList<Integer> pList, ArrayList<ArrayList<Integer>> result){ if(pList.size()==nums.size()){ ArrayList<Integer> al = new ArrayList<Integer>(); al.addAll(pList); result.add(al); return; }  //main body:all number, permute with permutation of rest numbers  for(Integer i:nums){ if(!pList.contains(i)){ pList.add(i); permuteRest(nums,pList,result); pList.remove(i); } } } }