Concise recursive Java


  • 2
    A
    private List<List<Integer>> res = new ArrayList<>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        addSubset(nums, 0, new ArrayList<Integer>());
        return res;
    }
    
    private void addSubset(int[] nums, int i, List<Integer> b) {
        res.add(b);
        for (int j = i; j < nums.length; j++) {
            List<Integer> c = new ArrayList<>(b);
            if (j == i || (j > i && nums[j] != nums[j-1])) {
                c.add(nums[j]);
                addSubset(nums, j+1, c);
            }
        }
    }

  • 0
    T

    Like the minimal branching, but a res.clear() is missing; how is this accepted?


  • 0
    A

    Why do we need to clear res? res is the output of the function, each subset is represented by array list c, which is a copy of b.


  • 0
    T

    I mean to clear it before the first addSubset call. Anyways, sorry, I was referring to this FAQ. I remembered that problems are tested like this:

    Solution x = new Solution();
    System.out.println(x.subsetsWithDup(new int[] {1})); // [[], [1]]
    System.out.println(x.subsetsWithDup(new int[] {2})); // [[], [1], [], [2]]
    

    and because you store state in a member variable it is merged to the second call and should have given you "Wrong Answer", but reading it again it looks like I misunderstood "using the same program instance" in the past and it indeed works, because it's called like this:

    System.out.println(new Solution().subsetsWithDup(new int[] {1})); // [[], [1]]
    System.out.println(new Solution().subsetsWithDup(new int[] {2})); // [[], [2]]

  • 0
    A

    I see, thanks for sharing, it's good to know. Well, in any case, the instance variable can be passed by reference in the recursive function. In fact, that would probably be a better approach - avoiding local state.


Log in to reply
 

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