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)

Full text and comments »

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