Permutations

Given a collection of distinct 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],
  [3,2,1]
]

 

public class Solution {
    //Given {1, 2, 3}
    //{1} 
    //{1, 2} & {2, 1}
    //{3, 1, 2}, {3, 2, 1} & {1, 3, 2}, {2, 3, 1} & {1, 2, 3} {2, 1, 3}
    //The good thing about ArrayList is that we can put element in a specific position
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); 
        if (nums.length == 0) return ans; 
        //Add the first element in l0
        List<Integer> l0 = new ArrayList<Integer>(); 
        l0.add(nums[0]);
        ans.add(l0);
        
        //add the rest of numbers to l0, to different position 
        for (int i = 1; i < nums.length; i++) {
            //Update version of ans
            List<List<Integer>> new_ans = new ArrayList<>(); 
            //different position: j
            for (int j = 0; j <= i; j++) {
                //different existing combinations: l
                for (List<Integer> l: ans) {
                    //copy l, and add num[i] to different positions in new_l 
                    List<Integer> new_l = new ArrayList<>(l); 
                    new_l.add(j, nums[i]);
                    new_ans.add(new_l);
                }
            }
            //gradually increase (incomplete) permutations
            ans = new_ans;
        }
        return ans;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s