Check Subset Sum Divisible by K (Dynamic Programming)

Problem Statement

Given an array of positive integers arr[] and an integer k, determine whether there exists at least one non-empty subset whose sum is divisible by k.

Example 1

Input:

Code

arr = [3, 1, 7, 5]
k = 6

Output:

Code

true

Explanation

Subset {7, 5} has sum:

Code

7 + 5 = 12
12 % 6 = 0

Hence, the answer is true.

Example 2

Input:

Code

arr = [1, 2, 6]
k = 5

Output:

Code

false

No subset produces a sum divisible by 5.

Why Not Brute Force?

For an array of size n, every element can either be included or excluded.

Therefore, the total number of subsets is:

Code

2^n

For each subset, we calculate the sum and check whether it is divisible by k.

Complexity

Time: O(2^n × n)
Space: O(1)

This approach is impractical for large values of n.

We need something better.

Key Observation

We are not interested in the exact subset sum.

We only care about:

Code

sum % k

For example, when:

Code

k = 6

Code

Sum = 8
8 % 6 = 2

Sum = 20
20 % 6 = 2

Although the sums are different, their remainder is the same.

This means we only need to remember the k possible remainders:

0
1
2
...
k - 1

Instead of storing large sums, we store only their remainder.

Dynamic Programming State

Create an array:

Java

boolean[] dp = new boolean[k];

Meaning

Code

dp[r] = true

There exists a non-empty subset whose sum gives remainder r.

Example

Suppose:

Code

k = 5

Code

Index : 0 1 2 3 4
Value : F T F T F

This means:

Some subset has remainder 1.
Some subset has remainder 3.

Initial State

Initially, no subset exists.

Code

Index : 0 1 2 3 4
Value : F F F F F

Processing Every Number

Suppose the current number is:

Code

num

There are two choices.

Choice 1: Start a New Subset

Take only the current element.

Example:

Code

num = 13
k = 5

Code

13 % 5 = 3

So,

Code

dp[3] = true

because the subset:

Code

{13}

exists.

Choice 2: Extend Existing Subsets

Suppose we already have:

Code

dp[2] = true

Meaning:

Some subset has remainder 2.

Now add the current number.

Suppose:

Code

num = 7

Code

7 % 5 = 2

The new remainder becomes:

Code

(2 + 7) % 5
= 9 % 5
= 4

Therefore:

Code

dp[4] = true

General Formula

Code

newRemainder = (oldRemainder + num) % k

Why Do We Clone the DP Array?

Suppose:

Code

dp =

F T F F F

Current number:

Code

If we directly update the same array,

dp[0] becomes true.

Later in the same iteration, that new value might again be used, meaning we accidentally use the same element multiple times.

To avoid this, we first copy the array:

Java

boolean[] next = dp.clone();

We update next.

After finishing all updates:

Java

dp = next;

Now every element is used exactly once.

Dry Run

Input

Code

arr = [3, 1, 7, 5]
k = 6

Initially

Code

Remainder: 0 1 2 3 4 5
DP:        F F F F F F

Process 3

Start a new subset:

Code

3 % 6 = 3

DP becomes:

Code

Remainder: 0 1 2 3 4 5
DP:        F F F T F F

Possible remainders:

Code

{3}

Process 1

Start a new subset:

Code

1 % 6 = 1

Current remainder:

Code

{1}

Extend the previous subset:

Code

3 + 1 = 4

Possible remainders become:

Code

{1, 3, 4}

DP:

Code

Remainder: 0 1 2 3 4 5
DP:        F T F T T F

Process 7

Start a new subset:

Code

7 % 6 = 1

Already exists.

Extend existing subsets:

Code

Possible remainders:

Code

{1, 2, 3, 4, 5}

Process 5

Start:

Code

5 % 6 = 5

Extend:

Code

1 + 5 = 6
6 % 6 = 0

We obtained remainder:

Code

This means a subset sum is divisible by 6.

Answer:

Code

true

Algorithm

For every element:

Clone the current DP array.
Mark the remainder of the current element.
Extend all existing subsets.
Replace the old DP array with the updated one.
If dp[0] == true, return true.

If every element is processed and remainder 0 never appears, return false.

Java Implementation

Java

class Solution {
    public boolean divisibleByK(int[] arr, int k) {

        boolean[] dp = new boolean[k];

        for (int num : arr) {

            boolean[] next = dp.clone();

            // Start a new subset
            next[num % k] = true;

            // Extend existing subsets
            for (int r = 0; r < k; r++) {
                if (dp[r]) {
                    next[(r + num) % k] = true;
                }
            }

            dp = next;

            // Found a subset divisible by k
            if (dp[0]) {
                return true;
            }
        }

        return false;
    }
}

Complexity Analysis

Time Complexity

For every element, we iterate over all k possible remainders.

Code

O(n × k)

Space Complexity

We maintain two arrays of size k.

Code

O(k)

Key Takeaways

We don't need the actual subset sums—only their remainders modulo k.
The DP array dp[r] records whether a non-empty subset with remainder r is achievable.
For each element, we either start a new subset or extend every previously reachable remainder.
Cloning the DP array ensures each element is used at most once, which is essential for subset problems.
This optimization reduces the solution from O(2ⁿ) brute force to O(n × k) time with O(k) space.

Summary

Instead of exploring every possible subset, this dynamic programming approach tracks only the possible remainders obtained after dividing subset sums by k. Since there are only k distinct remainders, the algorithm efficiently builds all reachable states by either starting a new subset or extending existing ones. This reduces the time complexity from exponential O(2ⁿ) to O(n × k) while using only O(k) additional space.