Given an array nums of n integers.Return sum of all subsets of the array nums.
Output can be printed in any order.
Input : nums = [2, 3]
Output : [0, 2, 3, 5]
Explanation :
When no elements is taken then Sum = 0.
When only 2 is taken then Sum = 2.
When only 3 is taken then Sum = 3.
When element 2 and 3 are taken then sum = 2+3 = 5.
Input : nums = [5, 2, 1]
Output : [0, 1, 2, 3, 5, 6, 7, 8]
Explanation :
When no elements is taken then Sum = 0.
When only 5 is taken then Sum = 5.
When only 2 is taken then Sum = 2.
When only 1 is taken then Sum = 1.
When element 2 and 1 are taken then sum = 2+1 = 3.
Input : nums = [1]
Consider a scenario where an individual is tasked with determining all possible expenditure amounts from a set of available items, each with a specific price. The process begins with an empty expenditure and involves evaluating each item sequentially. For each item, a decision is made whether to include its price in the current expenditure or not. This decision-making process continues until all items have been considered, resulting in a comprehensive list of all possible total expenditures.
In the recursive approach, the problem is decomposed into simpler sub-problems by making binary decisions for each item: either include the item in the current sum or exclude it. The recursion explores both possibilities for every item until all items are processed. The base case is reached when all items have been evaluated, at which point the accumulated sum is recorded. This method ensures that every potential combination of included and excluded items is considered, thereby generating all possible subset sums.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Helper function to calculate subset sums
void func(int ind, int sum, vector<int> &nums, vector<int> &ans) {
// Base case: if index reaches the end of the nums vector
if(ind == nums.size()) {
// Add the current sum to the ans vector
ans.push_back(sum);
return;
}
// Recursively include the current element in the sum
func(ind + 1, sum + nums[ind], nums, ans);
// Recursively exclude the current element from the sum
func(ind + 1, sum, nums, ans);
}
public:
// Function to generate all subset sums
vector<int> subsetSums(vector<int>& nums) {
vector<int> ans;
// Start the recursion with index 0 and initial sum 0
func(0, 0, nums, ans);
return ans;
}
};
int main() {
// Sample input vector
vector<int> nums = {1, 2, 3};
// Create an object of the Solution class
Solution sol;
// Call the subsetSums function and store the result
vector<int> result = sol.subsetSums(nums);
// Print the result
cout << "Subset sums are: ";
for (int sum : result) {
cout << sum << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> subsetSums(int[] nums) {
List<Integer> ans = new ArrayList<>();
// Start the recursion with index 0 and initial sum 0
func(0, 0, nums, ans);
return ans;
}
private void func(int ind, int sum, int[] nums, List<Integer> ans) {
// Base case: if index reaches the end of the nums array
if (ind == nums.length) {
// Add the current sum to the ans list
ans.add(sum);
return;
}
// Recursively include the current element in the sum
func(ind + 1, sum + nums[ind], nums, ans);
// Recursively exclude the current element from the sum
func(ind + 1, sum, nums, ans);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
List<Integer> result = sol.subsetSums(nums);
System.out.println("Subset sums are: " + result);
}
}
class Solution:
def subsetSums(self, nums):
def func(ind, sum, nums, ans):
# Base case: if index reaches the end of the nums list
if ind == len(nums):
# Add the current sum to the ans list
ans.append(sum)
return
# Recursively include the current element in the sum
func(ind + 1, sum + nums[ind], nums, ans)
# Recursively exclude the current element from the sum
func(ind + 1, sum, nums, ans)
ans = []
# Start the recursion with index 0 and initial sum 0
func(0, 0, nums, ans)
return ans
# Example usage
solution = Solution()
nums = [1, 2, 3]
result = solution.subsetSums(nums)
print("Subset sums are:", result)
class Solution {
subsetSums(nums) {
function func(ind, sum, nums, ans) {
// Base case: if index reaches the end of the nums array
if (ind === nums.length) {
// Add the current sum to the ans array
ans.push(sum);
return;
}
// Recursively include the current element in the sum
func(ind + 1, sum + nums[ind], nums, ans);
// Recursively exclude the current element from the sum
func(ind + 1, sum, nums, ans);
}
let ans = [];
// Start the recursion with index 0 and initial sum 0
func(0, 0, nums, ans);
return ans;
}
}
// Example usage
const solution = new Solution();
const nums = [1, 2, 3];
const result = solution.subsetSums(nums);
console.log("Subset sums are:", result);
Time Complexity: O(2N), where N is the size of the given array.
Each element has two possibilities (include or exclude), resulting in 2N combinations.
Space Complexity: O(2N)
The space needed to store all possible subset sums will take 2N space and the recursion stack space will take O(N).
Q: Why not generate all subsets explicitly?
A: Generating all subsets is computationally expensive for large n. Optimizing using the 2^n−1 contribution rule avoids this.
Q: How does each element contribute to 2^n−1 subsets?
A: In a set of size n, each element appears in exactly half of the 2^n subsets because subsets either include or exclude the element.
Q: What if subsets must be generated explicitly?
A: Use backtracking or bit masking to generate subsets and compute their sums. This may be required in specific scenarios where all subsets are needed.