Question

Print all subset sums of a given array recursively and iteratively.

ex) if the input is {1, 2, 3}, it should return {0,1,2,3,3,4,5,6}.

public int[] subsetSum1(int[] arr) { *recursive*}

public int[] subsetSum2(int[] arr) {*iterative*}

Answer 1

A. Recursive Approach to print all subset sums of a given array -

//Global variable to keep track of the current index of the result array
int index;

void subsetSumRecursive(int[] arr, int left, int right, int sum, int[] result) {    
    // Add the sum of the current subset to the result array
    if (left > right) { 
        result[index] = sum;
        index++;
        return; 
    } 
      
    // Subset that includes arr[left] 
    subsetSumRecursive(arr, left + 1, right, sum + arr[left], result); 
      
    // Subset that excludes arr[left] 
    subsetSumRecursive(arr, left + 1, right, sum, result); 
} 

public int[] subsetSum1 (int[] arr) {
    //Initialize necessary variables
    index = 0;
    int left = 0;
    int right = arr.length-1;
    int sum = 0;
    int index = 0;
    int[] result = new int[1000];

    //call the recursive method
    subsetSumRecursive(arr, left, right, sum, result);

    return result;
}

B. Iterative Approach to print all subset sums of a given array -

public int[] subsetSum2(int[] arr)  {  
    int n = arr.length;
    int[] result = new result[1000];
    int index = 0;

    // There are total 2^n subsets  possible
    int total = 1 << n;  
  
    // Considering all numbers from 0 to 2^n - 1  
    for(int i = 0; i < total; i++)  {  
       int sum = 0;  
         
       // Consider the binary form of the current number for deciding which of the array elements to select  
       for(int j = 0; j < n; j++)  
          if ((i & (1 << j)) != 0)  
              sum += arr[j];  
         
       // Add the sum of the selected elements to the result array 
       result[index] = sum;
       index++;
    }  

    return result;
}