Find K-Sum Subsets

Return all subset with whose sum is k

Subsets Summing to K

Problem Statement

Given a set of n positive integers, find all possible subsets of these integers that sum up to a target number, k.

Constraints

• 1 ≤ n ≤ 10
• 1 ≤ x ≤ 100, where x is any member of the input set
• 1 ≤ k ≤ 10³

Examples

Note: No examples were shared for this problem. Feel free to send them so they can be added here.

Solution

This solution uses the same bitmasking technique used for generating all subsets of a set (the power set), but adds a check to only keep the subsets whose numbers add up to k.

Steps

• If the input set has n numbers, there are 2ⁿ possible subsets in total. Each subset can be represented by a number from 0 to 2ⁿ - 1, written in binary. Each bit in this number tells us whether to include the number at that position.
• We loop through every number i from 0 to 2ⁿ - 1. Each one represents one possible subset.
• For each i, we check every bit position j (from 0 to arr.length - 1), using a helper function, getBit(num, bit):
  • This function shifts 1 to the left by bit positions, then checks if that bit is set (equal to 1) in num, using a bitwise AND operation.
  • If the bit is set, it means the number at that position should be included in this subset.
• As we build each subset, we also keep a running sum of its values.
• Once we've checked all the bit positions for a given i, we compare the subset's sum to our target, k. If they match, we add this subset to our results.
• After going through every possible subset, we return the full list of subsets whose sum equals k.

Code

class Solution {
    countSubset(arr, k) {

        function getBit(num, bit) {
            let mask = 1 << bit;
            return (num & mask) !== 0;
        }

        let result = [];
        let subsetsCount = 2 ** arr.length;

        for (let i = 0; i < subsetsCount; i++) {
            let subset = [];
            let sum = 0;

            for (let j = 0; j < arr.length; j++) {
                if (getBit(i, j)) {
                    subset.push(arr[j]);
                    sum += arr[j];
                }
            }

            if (sum === k) {
                result.push(subset);
            }
        }

        return result;
    }
}