Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Partition to K equal sum subsets

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
37 upvotes
Asked in companies
DunzoGoldman SachsMicrosoft

Problem statement

You are given an array of 'N' integers, and a positive integer 'K'. You need to determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of elements of each subset is equal.

Note:

1. The array can have duplicate elements.

2. Each of the array elements must belong to exactly one of the 'K' subsets.

3. The elements chosen for a subset may not be contiguous in the array.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N <= 15
0 <= NUMS[i] <= 10 ^ 3
1 <= K <= N

Where NUMS[i] denotes ith element of given array 'NUMS'.

Time Limit: 1 sec.
Sample Input 1:
1
8
4 3 1 3 4 3 1 2 
3
Sample Input 2:
True
Explanation for sample input 1:
It's possible to divide it into 3 subsets (4, 3), (1, 3, 3), (4, 2, 1) with equal sum = 7.
Sample Input 2:
1
7
5 1 2 6 7 1 2
4
Sample Output 2:
False
Full screen
Console