LeetCode problem #46 and #47 Permutations

46 Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution #1

1. Select a number from any position in the nums array and put it into the ans array, and remove the number that has been selected by nums.

2. Repeat the first step until the nums array is empty.

3. complete a set of answers, need to restore the number in the nums taht has been removed, and restore the number in ans that has been selected.
   

class Solution {
       public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> ans = new ArrayList();
        List<Integer> num = new ArrayList();
        for(int n : nums){
            num.add(n);
        }
        f(num,ans,res);
        return res;
    }

    public static void f(List<Integer> nums,List<Integer> ans,List<List<Integer>> res){
        if(nums.isEmpty()){
            res.add(new ArrayList<>(ans));
        }else{
            for(int i = 0;i<nums.size();i++){
                int n = nums.get(i);
                nums.remove(i);
                ans.add(n);
                ArrayList<Integer> integers = new ArrayList<>(nums);
                f(integers,ans,res);
                nums.add(i,n);
                ans.remove(ans.size() - 1);
            }
        }
    }
}

Solution #2

The solution #2 is similar to solution #1. Solution #2 does not require additional to store the answers, just swap the positions of the numbers in nums. Until the end of the nums array.

class Solution {
        public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        f(nums,0,res);
        return res;
    }

    public void f(int[] nums,int index,List<List<Integer>> res){
        if(index == nums.length){
            List<Integer> ans = new ArrayList();
            for(int i=0;i<nums.length;i++){
                ans.add(nums[i]);
            }
            res.add(ans);
        }else{
            for(int i=index;i<nums.length;i++){
                swap(nums,index,i);
                f(nums,index + 1,res);
                swap(nums,index,i);
            }
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

47. Permutations II

This question is an advanced level of "46.permutations". Asked to return the complete permutation that is not repeated.

Solution

Same solution as the previous question. Just add a set collection to record the numbers that has been visited.

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        f(nums,0,res);
        return res;
    }


    public void f(int[] nums,int index,List<List<Integer>> res){
        if(index == nums.length){
            List<Integer> ans = new ArrayList();
            for(int i=0;i<nums.length;i++){
                ans.add(nums[i]);
            }
            res.add(ans);
        }else{
            Set<Integer> vis = new HashSet();
            for(int i=index;i<nums.length;i++){
                if(!vis.contains(nums[i])){
                    vis.add(nums[i]);
                    swap(nums,index,i);
                    f(nums,index + 1,res);
                    swap(nums,index,i);
                }
            }
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}