Search code examples
javarecursionbacktracking

How to return the correct List<List<Integer>> in the subset backtracking problem

I am approaching a problem from Leetcode (78. Subsets). The method is correct, but I can't figure out how to return the correct answer.

I used the method I learned from an online course. I could accurately print out all the subsets when reaching the base case; however, I am not sure how to add those sublists into a result List<List<Integer>> and return it.

I declared a global variable and try to modify it directly, but all the subsets in it are empty. What is a good way for me to add the subsets to the result list and return it?

Here's the code:

class Solution {

    List<List<Integer>> result;

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> chosen = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();
        for (int i : nums){
            numbers.add(i);
        }
        result = new ArrayList<>();
        subsetsHelper(numbers, chosen);
        return result;
    }

    public void subsetsHelper(List<Integer> nums, List<Integer> chosen){
        if (nums.size() == 0){
            // System.out.println(chosen);
            result.add(chosen);
        }
        else{
            int x = nums.get(0);
            nums.remove(0);

            subsetsHelper(nums, chosen);

            chosen.add(x);
            subsetsHelper(nums, chosen);

            nums.add(0, x);
            chosen.remove(chosen.size()-1);
        }
    }
}

Here's the test case and output:

Your input
[1,2,3]
Output
[[],[],[],[],[],[],[],[]]
Expected
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Solution

  • The problem is this line

    result.add(chosen);

    basically you add chosen in result and then proceed to edit it in the next iterations. What you want to do is create a new list like so

    result.add(new ArrayList<>(chosen));

    EDIT: When you do result.add(chosen); you might think you store an arraylist chosen in result. But in fact you store the reference to the arraylist which chosen contains as its value. Adding a rough diagram to make things more clear

    enter image description here

    You might think chosen stores an entire ArrayList in itself but in reality, it just stores the reference to the arraylist which is stored in the java heap. When you make changes in chosen the changes will reflect at every place where the reference to this arraylist is stored, in your case it is in result.