Find K-Sum Subsets

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

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

Constraints:

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

Examples

Solution

function countSubset(arr, k) {

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

    let sets = [];
    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) {
            sets.push(subset);
        }
    }

    return sets;
}