2ms Java Solution


  • 0
    R
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); 
        boolean[] isIncluded = new boolean[nums.length];  // track entries which are included in current dfs path
        List<List<Integer>> soln = new ArrayList<List<Integer>>();
        dfs(nums, 0, isIncluded, soln);
        return soln;
    }
    public void dfs(int[] nums, int start, boolean[] isIncluded, List<List<Integer>> soln) {
        if (start == nums.length) {
            List<Integer> entry = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (isIncluded[i]) entry.add(nums[i]);
            }
            soln.add(entry);
            return;
        }
        isIncluded[start] = true;
        dfs(nums, start+1, isIncluded, soln);
        isIncluded[start] = false;
        int nextIndex = start+1;
        while (nextIndex < nums.length && nums[nextIndex] == nums[start]) {
            isIncluded[nextIndex++] = false;
        }
        dfs(nums, nextIndex, isIncluded, soln);
    }

Log in to reply
 

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