Use Recursion to get Subsets of an array. C++ and Java give me different results

Question

For example, given a set like below -

S=[1,3] 

we want to get the list of list with following values:

[[],[1],[3],[1,3]] 

I used C++ with the following code and it worked perfect for me. However, after I changed it to Java, the code didn't give me right results.

Any help? This is my Java code:

public static List<List<Integer>> subsetsRecursive(int[] nums){
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    if(nums.length == 0){
        return res;
    }
    ArrayList<Integer> itemList = new ArrayList<Integer>();

    dfs(res, itemList, 0, nums);

    return res;
}

private static void dfs(List<List<Integer>> res, ArrayList<Integer> temp, int end, int[] nums) {
    if(end == nums.length) {
        res.add(temp);
        return;
    }

    temp.add(nums[end]);
    dfs(res, temp, end+1, nums);
    temp.remove(temp.size()-1);
    dfs(res, temp, end+1, nums);   
}

And this is C++:

class Solution {
private:
    vector<vector<int> >res;
public:
    vector<vector<int> > subsets(vector<int> &S) {
        res.clear();

        vector<int>tmpres;
        dfs(S, 0, tmpres);
        return res;
    }
    void dfs(vector<int> &S, int iend, vector<int> &tmpres)
    {
        if(iend == S.size())
            {res.push_back(tmpres); return;}

        tmpres.push_back(S[iend]);
        dfs(S, iend+1, tmpres);
        tmpres.pop_back();

        dfs(S, iend+1, tmpres);
    }
};

Answer 1

In the line res.add(temp); temp is a reference.

You are adding a reference to the same list (itemList) every time you add it.

Try changing it to something list res.add(new ArrayList(temp)); so that it copies the list instead.