Groups With Equal Sums

Medium

You are given an array of positive integers values and an integer groups. Can all the numbers be distributed into exactly groups non-empty groups so that every group has the same sum? Each number goes into exactly one group. Return True or False.

Example 1

values=[6, 2, 4, 3, 3, 5, 1], groups=3 → True

The sum is 24, so each group needs 8: {6, 2}, {4, 3, 1}, {3, 5}.

Example 2

values=[5, 5, 2], groups=2 → False

The sum is 12, so each group needs 6, but nothing can top up a 5 to exactly 6.

Example 3

values=[7, 7, 7], groups=3 → True

Constraints

1 ≤ groups ≤ len(values) ≤ 16
1 ≤ values[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Memoization Array Dynamic Programming Backtracking Bitmask

Similar problems

Cheapest Basket with Bundles Medium Square Frame From Sticks Medium Seating by Divisibility Medium Least Total Walk to Scooters Medium Trainees and Coaches Medium

Input

values=[6, 2, 4, 3, 3, 5, 1], groups=3

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.