package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 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 _46 {

    public static class Solution1 {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList();
            result.add(new ArrayList<>());
            return backtracking(result, nums, 0);
        }

        private List<List<Integer>> backtracking(List<List<Integer>> result, int[] nums, int pos) {
            if (pos == nums.length) {
                return result;
            }
            List<List<Integer>> newResult = new ArrayList();
            for (List<Integer> eachList : result) {
                for (int i = 0; i <= eachList.size(); i++) {
                    //attn: i starts from 0
                    List<Integer> newList = new ArrayList(eachList);
                    newList.add(i, nums[pos]);
                    newResult.add(newList);
                }
            }
            result = newResult;
            return backtracking(result, nums, pos + 1);
        }
    }

}

@@ -563,23 +563,23 @@
 ing(
-result, nums, 0
+nums, 0, result
 );%0A 
@@ -637,16 +637,39 @@
 racking(
+int%5B%5D nums, int index, 
 List%3CLis
@@ -690,29 +690,8 @@
 sult
-, int%5B%5D nums, int pos
 ) %7B%0A
@@ -706,19 +706,21 @@
     if (
-pos
+index
  == nums
@@ -824,32 +824,34 @@
  = new ArrayList
+%3C%3E
 ();%0A            
@@ -955,52 +955,8 @@
 ) %7B%0A
-                    //attn: i starts from 0%0A
     
@@ -1008,16 +1008,18 @@
 rrayList
+%3C%3E
 (eachLis
@@ -1062,19 +1062,21 @@
 i, nums%5B
-pos
+index
 %5D);%0A    
@@ -1215,29 +1215,31 @@
 ing(
-result, nums, pos + 1
+nums, index + 1, result
 );%0A 

refactor 46