Permutation & Permutation II

Linkage

https://leetcode.com/problems/permutations/description/

Code

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        lens = len(nums)
        if lens == 0:
            return [[]]
        
        extant_items = [ [nums[0]] ]
        for i in range(1, lens):
            extant_items = self.generate_items(extant_items, nums[i])
            
        return extant_items
            
    def generate_items(self, extant_items, new_value):
        ret = []
        for item in extant_items:
            lens = len(item)
            for index in range(lens+1):
                new_item = item[:]
                new_item.insert(index, new_value)
                ret.append( new_item )
             
        return ret

FollowUp

https://leetcode.com/problems/permutations-ii/description/

In this implementation, we need the preprocessing to the original array, which means we should count the number of each elements.

import java.util.HashMap;

class Solution {
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> retArray = new ArrayList();
        HashMap<Integer, Integer> counter = new HashMap();
        
        for (int i = 0; i < nums.length; i++) {
            Integer item = counter.get(new Integer(nums[i]));
            if ( item == null){
                 counter.put( new Integer(nums[i]), 1 );
                 continue;
            }
            counter.put( new Integer(nums[i]), item+1);
        }
        List<Integer> permutate_array = new ArrayList<Integer>();
        helper(counter, permutate_array, retArray, nums.length);
        
        return retArray;
   }
    
    
    public void helper(HashMap<Integer, Integer> counter, List<Integer> permutate_array, List<List<Integer>> retArray, int depth){
        
        if (depth == 0) {
            retArray.add(permutate_array);
            return; 
        }
    
        for(Integer i : counter.keySet() ) {
            Integer count = counter.get(i);
            if (count > 0) {
                counter.put(i, count-1);
                List<Integer> new_permutate_array = new ArrayList<Integer>( permutate_array );
                new_permutate_array.add(i);
                helper(counter, new_permutate_array, retArray, depth-1);
                counter.put(i, count);
            }
        }
    }
}