Recursion and non-recursion Java solution for your reference


  • 4
    P

    Two solution, recursion and non-recursion:

    Recursion solution:

    public class Solution {
        Set<Integer> hash = new HashSet<>();
        List<List<Integer>> res = new ArrayList<>();
        int n;
        int[] nums;
        
        public void search(List<Integer> l, int p) {
            if (p == n) {
                int h = l.hashCode();
                if (!hash.contains(h)) {
                    hash.add(h);
                    res.add(new ArrayList<>(l));
                }
                return;
            }
            l.add(nums[p]);
            search(l, p+1);
            l.remove(l.size()-1);
            search(l, p+1);
        }
        
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            this.n = nums.length; this.nums = nums;
            Arrays.sort(nums);
            search(new ArrayList<Integer>(), 0);
            return res;
        }
    }
    

    Non-recursion solution:

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> temp = new ArrayList<>();
            res.add(temp);
            Arrays.sort(nums);
            int l = 0, k;
            for (int i = 0; i < nums.length; i++) {
                if (i == 0 || nums[i] != nums[i-1])
                    l = res.size();
                k = res.size();
                for (int j = k-l; j < k; j++) {
                    temp = new ArrayList<>(res.get(j));
                    temp.add(nums[i]);
                    res.add(temp);
                }
            }
            return res;
        }
    }

  • 1
    Y

    your non recursive method is clever. thank you.


Log in to reply
 

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