Time and Memory complexity using hashSet and backtrack?


  • 0
    H

    Can any one help me to analyze the time and memory complexity of my code using set and swap.
    What's the time and memory complexity if I want to use next permutation?

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new LinkedList<List<Integer>>();
            List<Integer> list = new LinkedList<Integer>();
            if (nums == null || nums.length == 0){
                return res;
            }
            permutation(nums, res, 0);
            return res;
        }
        public void permutation(int[] nums, List<List<Integer>> res, int index){
            if (index == nums.length - 1){
                List<Integer> list = new LinkedList<Integer>();
                for (int i : nums){
                    list.add(i);
                }
                res.add(list);
                return;
            }
            Set<Integer> set = new HashSet<Integer>();
            for (int i = index; i < nums.length; i++){
                if (set.contains(nums[i])){
                    continue;
                }
                set.add(nums[i]);
                swap(nums, index, i);
                permutation(nums, res, index + 1);
                swap(nums, index, i);
            }
        }
        public void swap(int[] nums, int i, int j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.