arpan_99's blog

By arpan_99, history, 19 months ago, In English

Question: Given a list arr of N integers, print sums of all subsets in it.

Input:

N = 2

arr[] = {2, 3}

Output:

0 2 3 5

Expected Time Complexity: O(2^N)

Expected Auxiliary Space: O(2^N)


Code —

class Solution
{
    
    int subset_sum(vector<int> arr, int n, int i, int sum, vector<int> &ans){
        if (i == n){
            return sum;
        }
        
        //including
        int x = subset_sum(arr, n, i+1, sum+arr[i], ans);
        ans.push_back(x);
        int y = subset_sum(arr, n, i+1, sum, ans);
        //not including
        ans.push_back(y);
    }    
        
public:
    vector<int> subsetSums(vector<int> arr, int n){
        sort(arr.begin(), arr.end()); 
        vector<int> ans;
        subset_sum(arr, n, 0, 0, ans);
        return ans;
    }
};

For Input:

2

1 1

Your Output:

-647528304 -647528304 0 1 1 2

Expected Output:

0 1 1 2

Please help me understand where are these garbage values coming from (-647528304, -647528304)

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

apart from the main bug, an important bug in your code is that you are not using references for passing the array to the function. due to this issue, the auxillary space needed would increase (far more than expected in many cases) to $$$O(n2^n)$$$.

EDIT: Due to deep copying, the time complexity increases to $$$O(n2^n)$$$ as well.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

on the main bug: I suggest that you draw how the call stack changes in a tree-like structure, and then where each output happens. Here is one way to fix:

How to fix
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your int subset_sum() function is missing a return value, so your code is UB.