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 {
        //this solution has a backtracking function that its return type is not void
        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++) {
                    List<Integer> newList = new ArrayList(eachList);
                    newList.add(i, nums[pos]);
                    newResult.add(newList);
                }
            }
            result = newResult;
            return backtracking(result, nums, pos + 1);
        }
    }

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

        private void recursive(List<List<Integer>> result, int[] nums, int pos) {
            if (pos == nums.length) {
                return;
            }
            List<List<Integer>> newResult = new ArrayList();
            for (List<Integer> eachList : result) {
                for (int i = 0; i <= eachList.size(); i++) {
                    List<Integer> newList = new ArrayList(eachList);
                    newList.add(i, nums[pos]);
                    newResult.add(newList);
                }
            }
            /**You'll have to use the two lines, instead of this line: result = newResult; otherwise, it won't work!!!*/
            result.clear();
            result.addAll(newResult);

            //then recursion
            recursive(result, nums, pos + 1);
        }
    }

}

@@ -373,93 +373,8 @@
 1 %7B%0A
-        //this solution has a backtracking function that its return type is not void%0A
     
@@ -418,32 +418,32 @@
 e(int%5B%5D nums) %7B%0A
+
             List
@@ -936,32 +936,55 @@
 t.size(); i++) %7B
+//attn: i starts from 0
 %0A               
@@ -1188,24 +1188,24 @@
  newResult;%0A
+
             
@@ -1269,1082 +1269,6 @@
  %7D%0A%0A
-    public static class Solution2 %7B%0A        public List%3CList%3CInteger%3E%3E permute(int%5B%5D nums) %7B%0A            List%3CList%3CInteger%3E%3E result = new ArrayList();%0A            result.add(new ArrayList%3C%3E());%0A            recursive(result, nums, 0);%0A            return result;%0A        %7D%0A%0A        private void recursive(List%3CList%3CInteger%3E%3E result, int%5B%5D nums, int pos) %7B%0A            if (pos == nums.length) %7B%0A                return;%0A            %7D%0A            List%3CList%3CInteger%3E%3E newResult = new ArrayList();%0A            for (List%3CInteger%3E eachList : result) %7B%0A                for (int i = 0; i %3C= eachList.size(); i++) %7B%0A                    List%3CInteger%3E newList = new ArrayList(eachList);%0A                    newList.add(i, nums%5Bpos%5D);%0A                    newResult.add(newList);%0A                %7D%0A            %7D%0A            /**You'll have to use the two lines, instead of this line: result = newResult; otherwise, it won't work!!!*/%0A            result.clear();%0A            result.addAll(newResult);%0A%0A            //then recursion%0A            recursive(result, nums, pos + 1);%0A        %7D%0A    %7D%0A%0A
 %7D%0A

add note for 46