# 46 Permutations

Concept:

以[1,2,3]為例

觀察 讀到1時，將1放入ans

讀到2時，取出ans中的entry，將2放在位置0，產生21，將2放在位置1，產生12

讀到3時，取出ans中的entry，21，將3放在位置0,1,2產生321,231,213，

取出12，將3放在位置0,1,2產生312,132,123。

Pseudocode:

        List<List<Integer>> ans
        add [nums[0]] to ans
        for each element in nums
            List<List<Integer>> newAns
            for each possible positions for current element
                for each entry in ans
                    List<Integer> tmp = ans.get(k)
                    tmp.add(j,nums[i])
                    newAns.add(tmp)
            ans = newAns
        return ans;

Code:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> ans=new ArrayList<>();
        ans.add(Arrays.asList(nums[0]));
        for(int i=1; i<nums.length; i++){
            List<List<Integer>> newAns = new ArrayList<>();
            for(int j=0; j<=i; j++){
                for(int k=0; k<ans.size(); k++){
                    List<Integer> tmp = new ArrayList<>(ans.get(k));
                    tmp.add(j,nums[i]);
                    newAns.add(tmp);
                }
            }
            ans = newAns;
        }
        return ans;
    }
}