Subset Sum Equal to K
Given a list of integers nums and an integer k, determine whether any subset of the list has a sum equal to k.
Each element may be selected at most once. A subset does not need to contain consecutive elements. The empty subset is allowed and has a sum of 0.
Method Signature
boolean subsetSum(List<Integer> nums, int k)
nums contains the integers available for selection.k is the required subset sum.- Return
true if at least one subset sums to k; otherwise, return false.
Bit Masking Requirement
Represent each possible subset using a bit mask. For a mask, the bit at index i determines whether nums[i] is included in the subset.
Examine all 2n possible subsets, where n is the number of elements in nums.
Constraints
1 ≤ nums.size() ≤ 20-1,000,000 ≤ nums[i] ≤ 1,000,000-10,000,000 ≤ k ≤ 10,000,000- Each list position represents a separate selectable element.
Expected Complexity
- Time complexity:
O(n * 2n)
- Extra space complexity:
O(1)
Examples
Example 1
subsetSum(nums = [3, 8, 11, 14], k = 19)
Output: true
The subset containing 8 and 11 has a sum of 19.
Example 2
subsetSum(nums = [4, 7, 13], k = 10)
Output: false
No subset of the given elements has a sum equal to 10.
Example 3
subsetSum(nums = [-6, 2, 9, 12], k = 5)
Output: true
The subset containing -6, 2, and 9 has a sum of 5.
Example 4
subsetSum(nums = [5, 10, 15], k = 0)
Output: true
The empty subset has a sum of 0.