698. Partition to K Equal Sum Subsets - Solution

The problem

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Constraints:

1 <= k <= nums.length <= 16
1 <= nums[i] <= 10⁴
The frequency of each element is in the range [1, 4].

Approach overview

Problem Overview: You get an integer array nums and an integer k. The task is to determine whether the array can be split into exactly k subsets where every subset has the same total sum. Each element must belong to exactly one subset.

The first observation: if the total array sum is not divisible by k, the answer is immediately false. If it is divisible, each subset must sum to target = totalSum / k. The challenge becomes assigning numbers to k buckets so that every bucket reaches this target without reusing elements.

Approach 1: Backtracking with Target Subset Sum (Time: O(k * 2^n), Space: O(n))

This approach builds subsets recursively using backtracking. Sort the array in descending order, then try to place each number into one of the k buckets. Maintain an array representing the current sum of every bucket. For each number, iterate through the buckets and attempt to place it if the new sum does not exceed the target.

The key insight is aggressive pruning. If placing a number into an empty bucket fails, there is no reason to try other empty buckets because they are symmetric. Sorting the array largest-first also reduces branching since larger values constrain placements earlier. This drastically cuts the search space and works well for the constraint n ≤ 16. The algorithm effectively explores subset combinations while ensuring each bucket never exceeds the target.

Approach 2: Dynamic Programming with State Compression (Time: O(n * 2^n), Space: O(2^n))

This approach uses dynamic programming with bitmasking to represent which elements are already used. A bitmask of size n indicates selected elements, and the DP value stores the current subset sum modulo the target. Iterate through all masks and try to add another unused element.

If adding nums[i] keeps the subset sum ≤ target, transition to the new mask. When the partial sum reaches the target, reset it to zero to start building the next subset. If the final mask (1< is reachable, all elements were partitioned successfully.

The state compression technique avoids explicit bucket tracking and instead encodes subset membership in bits. This produces a deterministic O(n * 2^n) solution and works well for smaller arrays where bitmask DP is feasible.

Recommended for interviews: Start with the Backtracking with Target Subset Sum approach. It demonstrates strong problem decomposition, pruning strategies, and recursive reasoning. Interviewers commonly expect this solution. The bitmask DP version shows deeper knowledge of 2^n state compression and is a strong follow-up optimization when discussing advanced techniques.

Approach 1: Backtracking with Target Subset Sum

This approach involves using backtracking to attempt to build k subsets, each with a sum equal to totalSum / k. The decision tree can be pruned by sorting the numbers in decreasing order and tracking the sums of the current subset.

Python

from typing import List

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        target_sum = total_sum // k
        nums.sort(reverse=True)
        subsets = [0] * k
        return self.can_partition(nums, subsets, target_sum, 0)

    def can_partition(self, nums: List[int], subsets: List[int], target: int, index: int) -> bool:
        if index == len(nums):
            return True
        curr = nums[index]
        for i in range(len(subsets)):
            if subsets[i] + curr <= target:
                subsets[i] += curr
                if self.can_partition(nums, subsets, target, index + 1):
                    return True
                subsets[i] -= curr
            if subsets[i] == 0:
                break
        return False

# Example usage:
solution = Solution()
print(solution.canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4))

Java

import java.util.Arrays;

public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;
        Arrays.sort(nums);
        return canPartition(nums, new int[k], nums.length - 1, targetSubsetSum);
    }

    private boolean canPartition(int[] nums, int[] subsetSums, int index, int targetSubsetSum) {
        if (index < 0) return true;
        int currVal = nums[index];
        for (int i = 0; i < subsetSums.length; i++) {
            if (subsetSums[i] + currVal <= targetSubsetSum) {
                subsetSums[i] += currVal;
                if (canPartition(nums, subsetSums, index - 1, targetSubsetSum)) return true;
                subsetSums[i] -= currVal;
            }
            if (subsetSums[i] == 0) break;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 3, 2, 3, 5, 2, 1};
        int k = 4;
        System.out.println(sol.canPartitionKSubsets(nums, k));
    }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    bool canPartitionKSubsets(std::vector<int>& nums, int k) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;
        std::sort(nums.begin(), nums.end(), std::greater<int>());
        std::vector<int> subsetSums(k, 0);
        return canPartition(nums, subsetSums, targetSubsetSum, 0);
    }

private:
    bool canPartition(std::vector<int>& nums, std::vector<int>& subsetSums, int targetSubsetSum, int index) {
        if (index == nums.size()) return true;
        for (int i = 0; i < subsetSums.size(); i++) {
            if (subsetSums[i] + nums[index] <= targetSubsetSum) {
                subsetSums[i] += nums[index];
                if (canPartition(nums, subsetSums, targetSubsetSum, index + 1)) return true;
                subsetSums[i] -= nums[index];
            }
            if (subsetSums[i] == 0) break;
        }
        return false;
    }
};

JavaScript

function canPartitionKSubsets(nums, k) {
    const totalSum = nums.reduce((a, b) => a + b, 0);
    if (totalSum % k !== 0) return false;
    const targetSubsetSum = totalSum / k;
    nums.sort((a, b) => b - a);
    const subsetSums = new Array(k).fill(0);
    return canPartition(nums, subsetSums, targetSubsetSum, 0);

    function canPartition(nums, subsetSums, target, index) {
        if (index === nums.length) return true;
        for (let i = 0; i < subsetSums.length; i++) {
            if (subsetSums[i] + nums[index] <= target) {
                subsetSums[i] += nums[index];
                if (canPartition(nums, subsetSums, target, index + 1)) return true;
                subsetSums[i] -= nums[index];
            }
            if (subsetSums[i] === 0) break;
        }
        return false;
    }
}

console.log(canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

bool canPartition(int* nums, int numsSize, int k, int* subsetSums, int targetSubsetSum, int index) {
    if (index == numsSize) return true;
    for (int i = 0; i < k; i++) {
        if (subsetSums[i] + nums[index] <= targetSubsetSum) {
            subsetSums[i] += nums[index];
            if (canPartition(nums, numsSize, k, subsetSums, targetSubsetSum, index + 1)) return true;
            subsetSums[i] -= nums[index];
        }
        if (subsetSums[i] == 0) break; // Avoid trying same state again
    }
    return false;
}

bool canPartitionKSubsets(int* nums, int numsSize, int k) {
    int totalSum = 0;
    for (int i = 0; i < numsSize; i++) totalSum += nums[i];
    if (totalSum % k != 0) return false;
    int targetSubsetSum = totalSum / k;
    qsort(nums, numsSize, sizeof(int), compare);
    int* subsetSums = (int*)calloc(k, sizeof(int));
    bool result = canPartition(nums, numsSize, k, subsetSums, targetSubsetSum, 0);
    free(subsetSums);
    return result;
}

int main() {
    int nums[] = {4, 3, 2, 3, 5, 2, 1};
    int k = 4;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", canPartitionKSubsets(nums, numsSize, k) ? "true" : "false");
    return 0;
}

using System;

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int totalSum = 0;
        foreach (var num in nums) totalSum += num;
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        int[] subsetSums = new int[k];
        return CanPartition(nums, subsetSums, targetSubsetSum, 0);
    }

    private bool CanPartition(int[] nums, int[] subsetSums, int targetSubsetSum, int index) {
        if (index == nums.Length) return true;
        for (int i = 0; i < subsetSums.Length; i++) {
            if (subsetSums[i] + nums[index] <= targetSubsetSum) {
                subsetSums[i] += nums[index];
                if (CanPartition(nums, subsetSums, targetSubsetSum, index + 1)) return true;
                subsetSums[i] -= nums[index];
            }
            if (subsetSums[i] == 0) break;
        }
        return false;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CanPartitionKSubsets(new int[] { 4, 3, 2, 3, 5, 2, 1 }, 4));
    }
}

The Python approach also employs backtracking. Sorting the array before to ensure that larger numbers are considered first for the subsets aids in significantly cutting down on unnecessary recursive calls, improving the effective backtracking.

Complexity

Time Complexity: O(kⁿ), factoring in the worst-case scenario where every option is examined.
Space Complexity: O(k) due to storage needed for subset sums.

Try this approach in the editor

Approach 2: Dynamic Programming and State Compression

A less intuitive but potentially powerful technique involves using bitmasking to represent subsets and top-down dynamic programming to evaluate the feasibility of partitioning. This uses state compression where each state represents a set of elements already partitioned; 1 means used, 0 means unused.

Java

import java.util.Arrays;

public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int totalSum = Arrays.stream(nums).sum();
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;

        int n = nums.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= targetSubsetSum) {
                    int newMask = mask | (1 << i);
                    dp[newMask] = (dp[mask] + nums[i]) % targetSubsetSum;
                }
            }
        }

        return dp[(1 << n) - 1] == 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4));
    }
}

C++

#include <vector>
#include <cstring>

class Solution {
public:
    bool canPartitionKSubsets(std::vector<int>& nums, int k) {
        int totalSum = 0, n = nums.size();
        for (int num : nums) totalSum += num;
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;

        std::vector<int> dp(1 << n, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= targetSubsetSum) {
                    int newMask = mask | (1 << i);
                    dp[newMask] = (dp[mask] + nums[i]) % targetSubsetSum;
                }
            }
        }

        return dp[(1 << n) - 1] == 0;
    }
};

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int dp[1 << 16], maskSum[1 << 16];

bool canPartitionKSubsets(int* nums, int numsSize, int k) {
    int totalSum = 0;
    for (int i = 0; i < numsSize; ++i) totalSum += nums[i];
    if (totalSum % k != 0) return false;
    int targetSubsetSum = totalSum / k;

    memset(dp, -1, sizeof(dp));
    int allMask = (1 << numsSize) - 1;
    dp[0] = 0;

    // Traverse all states
    for (int mask = 0; mask <= allMask; ++mask) {
        if (dp[mask] == -1) continue;
        for (int j = 0; j < numsSize; ++j) {
            if (!(mask & (1 << j)) && dp[mask] + nums[j] <= targetSubsetSum) {
                int newMask = mask | (1 << j);
                dp[newMask] = (dp[mask] + nums[j]) % targetSubsetSum;
            }
        }
    }

    return dp[allMask] == 0;
}

int main() {
    int nums[] = {4, 3, 2, 3, 5, 2, 1};
    int k = 4;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", canPartitionKSubsets(nums, numsSize, k) ? "true" : "false");
    return 0;
}

In this Java DP with bitmasking solution, bit shifts represent which numbers are in or out of a subset configuration. This method ensures each subset sum is proper modulo targetSubsetSum by using DP states. The state-mask expresses the current subset configuration as elements included or excluded.

Complexity

Time Complexity: O(n * 2ⁿ), due to the comprehensive search across state configurations.
Space Complexity: O(2ⁿ), for storing each state's result derived from subset presence or absence.

Try this approach in the editor

Approach 3: DFS + Pruning

According to the problem description, we need to partition the array nums into k subsets such that the sum of each subset is equal. Therefore, we first sum all the elements in nums. If the total sum cannot be divided by k, it means we cannot partition the array into k subsets, and we return false early.

If the total sum can be divided by k, let's denote the expected sum of each subset as s. Then, we create an array cur of length k to represent the current sum of each subset.

We sort the array nums in descending order (to reduce the number of searches), and then start from the first element, trying to add it to each subset in cur one by one. If adding nums[i] to a subset cur[j] makes the subset's sum exceed s, it means it cannot be placed in that subset, and we can skip it. Additionally, if cur[j] is equal to cur[j - 1], it means we have already completed the search for cur[j - 1], and we can skip the current search.

If we can add all elements to cur, it means we can partition the array into k subsets, and we return true.

TypeScript

function canPartitionKSubsets(nums: number[], k: number): boolean {
    const dfs = (i: number): boolean => {
        if (i === nums.length) {
            return true;
        }
        for (let j = 0; j < k; j++) {
            if (j > 0 && cur[j] === cur[j - 1]) {
                continue;
            }
            cur[j] += nums[i];
            if (cur[j] <= s && dfs(i + 1)) {
                return true;
            }
            cur[j] -= nums[i];
        }
        return false;
    };

    let s = nums.reduce((a, b) => a + b, 0);
    const mod = s % k;
    if (mod !== 0) {
        return false;
    }
    s = Math.floor(s / k);
    const cur = Array(k).fill(0);
    nums.sort((a, b) => b - a);
    return dfs(0);
}

func canPartitionKSubsets(nums []int, k int) bool {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s%k != 0 {
		return false
	}
	s /= k
	cur := make([]int, k)
	n := len(nums)

	var dfs func(int) bool
	dfs = func(i int) bool {
		if i == n {
			return true
		}
		for j := 0; j < k; j++ {
			if j > 0 && cur[j] == cur[j-1] {
				continue
			}
			cur[j] += nums[i]
			if cur[j] <= s && dfs(i+1) {
				return true
			}
			cur[j] -= nums[i]
		}
		return false
	}

	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	return dfs(0)
}

Try this approach in the editor

Approach 4: State Compression + Memoization

Similar to Solution 1, we first check whether the array nums can be partitioned into k subsets. If it cannot be divided by k, we directly return false.

Let s be the expected sum of each subset, and let state represent the current partitioning state of the elements. For the i-th number, if the i-th bit of state is 0, it means the i-th element has not been partitioned.

Our goal is to form k subsets with a sum of s from all elements. Let t be the current sum of the subset. When the i-th element is not partitioned:

If t + nums[i] \gt s, it means the i-th element cannot be added to the current subset. Since we sort the array nums in ascending order, all elements from position i onwards cannot be added to the current subset, and we directly return false.
Otherwise, add the i-th element to the current subset, change the state to state | 2^i, and continue searching for unpartitioned elements. Note that if t + nums[i] = s, it means we can form a subset with a sum of s. The next step is to reset t to zero (which can be achieved by (t + nums[i]) bmod s) and continue partitioning the next subset.

To avoid repeated searches, we use an array f of length 2^n to record the search results for each state. The array f has three possible values:

0 indicates that the current state has not been searched yet;
-1: indicates that the current state cannot be partitioned into k subsets;
1: indicates that the current state can be partitioned into k subsets.

The time complexity is O(n times 2^n), and the space complexity is O(2^n). Here, n represents the length of the array nums. For each state, we need to traverse the array nums, which has a time complexity of O(n). The total number of states is 2^n, so the overall time complexity is O(n times 2^n).

TypeScript

function canPartitionKSubsets(nums: number[], k: number): boolean {
    let s = nums.reduce((a, b) => a + b, 0);
    if (s % k !== 0) {
        return false;
    }
    s = Math.floor(s / k);
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const mask = (1 << n) - 1;
    const f = Array(1 << n).fill(0);

    const dfs = (state: number, t: number): boolean => {
        if (state === mask) {
            return true;
        }
        if (f[state] !== 0) {
            return f[state] === 1;
        }
        for (let i = 0; i < n; ++i) {
            if ((state >> i) & 1) {
                continue;
            }
            if (t + nums[i] > s) {
                break;
            }
            if (dfs(state | (1 << i), (t + nums[i]) % s)) {
                f[state] = 1;
                return true;
            }
        }
        f[state] = -1;
        return false;
    };

    return dfs(0, 0);
}

func canPartitionKSubsets(nums []int, k int) bool {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s%k != 0 {
		return false
	}
	s /= k
	n := len(nums)
	f := make([]int, 1<<n)
	mask := (1 << n) - 1

	var dfs func(int, int) bool
	dfs = func(state, t int) bool {
		if state == mask {
			return true
		}
		if f[state] != 0 {
			return f[state] == 1
		}
		for i, v := range nums {
			if (state >> i & 1) == 1 {
				continue
			}
			if t+v > s {
				break
			}
			if dfs(state|1<<i, (t+v)%s) {
				f[state] = 1
				return true
			}
		}
		f[state] = -1
		return false
	}

	sort.Ints(nums)
	return dfs(0, 0)
}

Try this approach in the editor

Approach 5: Dynamic Programming

We can use dynamic programming to solve this problem.

We define f[i] to represent whether there exists k subsets that meet the requirements when the current selected numbers' state is i. Initially, f[0] = true, and the answer is f[2^n - 1], where n is the length of the array nums. Additionally, we define cur[i] to represent the sum of the last subset when the current selected numbers' state is i.

We enumerate the states i in the range [0, 2^n]. For each state i, if f[i] is false, we skip it. Otherwise, we enumerate any number nums[j] in the array nums. If cur[i] + nums[j] > s, we break the enumeration loop because the subsequent numbers are larger and cannot be placed in the current subset. Otherwise, if the j-th bit of the binary representation of i is 0, it means the current nums[j] has not been selected. We can place it in the current subset, change the state to i | 2^j, update cur[i | 2^j] = (cur[i] + nums[j]) bmod s, and set f[i | 2^j] = true.

Finally, we return f[2^n - 1].

The time complexity is O(n times 2^n), and the space complexity is O(2^n). Here, n represents the length of the array nums.

TypeScript

function canPartitionKSubsets(nums: number[], k: number): boolean {
    let s = nums.reduce((a, b) => a + b);
    if (s % k !== 0) {
        return false;
    }
    s /= k;
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const f: boolean[] = Array(1 << n).fill(false);
    f[0] = true;
    const cur: number[] = Array(n).fill(0);
    for (let i = 0; i < 1 << n; ++i) {
        if (!f[i]) {
            continue;
        }
        for (let j = 0; j < n; ++j) {
            if (cur[i] + nums[j] > s) {
                break;
            }
            if (((i >> j) & 1) === 0) {
                f[i | (1 << j)] = true;
                cur[i | (1 << j)] = (cur[i] + nums[j]) % s;
            }
        }
    }
    return f[(1 << n) - 1];
}

func canPartitionKSubsets(nums []int, k int) bool {
	s := 0
	for _, x := range nums {
		s += x
	}
	if s%k != 0 {
		return false
	}
	s /= k
	sort.Ints(nums)
	n := len(nums)
	f := make([]bool, 1<<n)
	cur := make([]int, 1<<n)
	f[0] = true
	for i := 0; i < 1<<n; i++ {
		if !f[i] {
			continue
		}
		for j := 0; j < n; j++ {
			if cur[i]+nums[j] > s {
				break
			}
			if i>>j&1 == 0 {
				f[i|1<<j] = true
				cur[i|1<<j] = (cur[i] + nums[j]) % s
			}
		}
	}
	return f[(1<<n)-1]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Backtracking with Target Subset Sum	Time Complexity: O(kⁿ), factoring in the worst-case scenario where every option is examined. Space Complexity: O(k) due to storage needed for subset sums.
Dynamic Programming and State Compression	Time Complexity: O(n * 2ⁿ), due to the comprehensive search across state configurations. Space Complexity: O(2ⁿ), for storing each state's result derived from subset presence or absence.
DFS + Pruning	–
State Compression + Memoization	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking with Target Subset Sum	O(k * 2^n)	O(n)	Best general solution. Works well with pruning and small n (≤16).
Dynamic Programming with Bitmask (State Compression)	O(n * 2^n)	O(2^n)	Useful when representing subsets with bitmasks or discussing advanced DP optimizations.

Frequently asked questions

Is Partition to K Equal Sum Subsets easy or hard?

Partition to K Equal Sum Subsets is considered Medium on LeetCode but often feels closer to Hard for beginners. The difficulty comes from pruning the exponential search space and recognizing patterns like bucket filling or bitmask DP.

Partition to K Equal Sum Subsets Python or Java solution?

Python and Java implementations usually follow the same pattern: compute the target subset sum, sort the array descending, and use recursive backtracking to place numbers into k buckets. Bitmask DP versions are also common in Java and C++ because bit operations are efficient.

How to solve Partition to K Equal Sum Subsets in O(n * 2^n)?

Use dynamic programming with bitmask state compression. Each mask represents which elements are already used. The DP state stores the current subset sum modulo the target value. Transition by adding unused elements while keeping the partial sum ≤ target. Reaching the full mask means all numbers were partitioned successfully.

What is the best approach for Partition to K Equal Sum Subsets?

Backtracking with target subset sums is the most common approach. Sort the array in descending order and recursively assign numbers to k buckets while keeping each bucket's sum ≤ target. With pruning and symmetry checks, the search space reduces significantly. Time complexity is roughly O(k * 2^n) with O(n) recursion space.

Is Partition to K Equal Sum Subsets asked at Google Amazon Meta?

Partition to K Equal Sum Subsets appears frequently in interviews at companies that test recursion and combinatorial search, including Google, Amazon, and Meta-style interview prep sets. The problem evaluates backtracking optimization, pruning strategies, and understanding of subset state representations.

What data structure is used in Partition to K Equal Sum Subsets?

The typical solution uses arrays to track bucket sums and recursion for backtracking. Advanced implementations also use bitmasks and hash-based memoization to store visited subset states, enabling dynamic programming with compressed state representation.

What is the time complexity of Partition to K Equal Sum Subsets?

The optimized backtracking solution runs in about O(k * 2^n) time because it explores subset combinations while pruning invalid states. The dynamic programming solution with bitmask state compression runs in O(n * 2^n) time and uses O(2^n) memory for DP states.

Partition to K Equal Sum Subsets solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Target Subset Sum

Approach 2: Dynamic Programming and State Compression

Approach 3: DFS + Pruning

Approach 4: State Compression + Memoization

Approach 5: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Partition to K Equal Sum Subsets solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Target Subset Sum

Approach 2: Dynamic Programming and State Compression

Approach 3: DFS + Pruning

Approach 4: State Compression + Memoization

Approach 5: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems