take-or-not-take approach


  • 0
    Z
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> list = new ArrayList<>();
            dfs(list, nums, new ArrayList<>(), 0);
            return list;
        }
    
       private void dfs(List<List<Integer>> result, int[] nums, List<Integer> cur, int pos) {
            int n = nums.length;
            if (pos == n) {
                result.add(new ArrayList<>(cur));
                return;
            }
    
            cur.add(nums[pos]);
            dfs(result, nums, cur, pos + 1);
            cur.remove(cur.size() - 1);
    
            //don't take this number
            int nextPos = pos + 1;
            while (nextPos < n && nums[nextPos] == nums[pos]) {
                nextPos++;
            }
            dfs(result, nums, cur, nextPos);
        }
    

Log in to reply
 

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