Problem:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Method 1:

Backtracking. This is a NP problem. We use recursive loop to solve it. Before recursive method, add sth. But after the recursion method, we need to protect the scene and remove what had been added.

Code for method 1:

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] nums) {
        ArrayList<Integer> item = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> used = new ArrayList<Integer>();
        if (nums.length == 0) return res;
        return helper(res, item, used, nums);
    }
    
    public ArrayList<ArrayList<Integer>> helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item, ArrayList<Integer> used, int[] nums){
        if (item.size() == nums.length){
            res.add(new ArrayList<Integer>(item));  // this is important. can not to be res.add(item), since we still keep the reference to item and may change it in the future.
            return res;
        }
        
        for (int i = 0; i < nums.length; i++){
            if (!used.contains(nums[i])){
                item.add(nums[i]);
                used.add(nums[i]);
                helper(res, item, used, nums);
                item.remove(item.size()-1);
                used.remove(used.size()-1);
            }
        }
        return res;
        
    }
    
}

Method 2:

Iterative method.

For 1 element, get all possible combinations.

For 2 elements, get all possible combinations.

….

For all elements, get all possible combinations.

Code for method 2:


public class Solution {
    public ArrayList< ArrayList<Integer>> permute(int[] nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length == 0) return res;
        ArrayList<Integer> item = new ArrayList<Integer>();
        item.add(nums[0]);
        res.add(item);
        
        for (int i = 1; i < nums.length; i++){
            ArrayList<ArrayList<Integer>> newres = new ArrayList<ArrayList<Integer>>();
            for (int j = 0; j < res.size(); j++){
                ArrayList<Integer> temp = res.get(j);
                for (int k = 0; k < temp.size() + 1; k++){
                    ArrayList<Integer> newItem = new ArrayList<Integer>(temp);
                    newItem.add(k,nums[i]);
                    newres.add(newItem);
                }
            }
            res = newres;
        }
        return res;
    }
}