奇数 横竖斜总和相等

Description:

描述：

This is a standard interview problem to make partitions for k subsets each of them having equal sum using backtracking.

这是一个标准的采访问题，它使用回溯来使k个子集的分区具有相等的总和。

Problem statement:

问题陈述：

A set is given. You have to make K subsets by which all of the subsets have equal sum.

给出一个集合。 您必须制作所有子集具有相等总和的K个子集。

Test case T    // T no. of line with the value of N and corresponding values and the value of K.        E.g.    2        29    71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65 29 42 51 94 1 35 65 25 15 88 57 44     2    15    29 28 51 85 59 21 25 23 70 97 82 31 85 93 73     3        Constraints:    1<=T<=100    1<=N,K<=100    1<=Set[] <=100        Output:    Print T lines either Partition possible or Partition is not possible.

Example

例

Input:    N=15    Set[]= { 29 28 51 85 59 21 25 23 70 97 82 31 85 93 }    K=3        Then the subsets are:    {85,21,23,70,85}    {28,59,31,93,73}    {29,51,25,97,82}    Output:    Partition possible

Explanation with example

举例说明

Let there is a set of N positive numbers X₁, X₂, X₃, ..., X_n.

设一组N个正数X ₁ ，X ₂ ，X ₃ ，...，X _n 。

To make K no. of subset with equal sum is a problem of combination and we solve it using backtracking. We will follow some possible path to solve this problem.

使K号。 总和相等的子集的组合是组合的问题，我们使用回溯来解决。 我们将遵循一些可能的途径来解决此问题。

1. If the K equals to 1 then it always true and the value of K is greater than N then it is impossible so it is false then.

   如果K等于1，则它始终为true，并且K的值大于N ，则不可能，因此为false。

2. We will sum up all the values

   and divide the Sum by
   K.

   我们将总结所有的价值 K。

3. If the sum is fully divisible by k then we will go to the step 4 otherwise it is false.

   如果总和可以被k整除，那么我们将转到步骤4，否则为假。

4. We will take a Boolean array to identify the values which are already been used.

   我们将使用一个布尔数组来标识已使用的值。

5. Firstly, we will go for the first subset which has the sum equals to (Sum/K) and make the mark which of the elements are taken consideration.

   首先，我们将寻找第一个子集，其总和等于( Sum / K )，并标记要考虑的元素。

6. After getting the first subset we will go for the other but in that case will not consider the numbers which are already been used for the first subset and those are indicated by the Boolean array.

   在获得第一个子集之后，我们将继续寻找另一个子集，但是在那种情况下，将不考虑已经用于第一个子集的数字，这些数字由布尔数组表示。

7. For the last subset will not go for the search because all the remaining numbers must have the sum equals to (Sum/K).

   对于最后一个子集，将不进行搜索，因为所有其余数字的总和必须等于( Sum / K )。

For the input,

对于输入，

N = 15    Set[] = { 29 28 51 85 59 21 25 23 70 97 82 31 85 93 }    K = 3

Firstly, we calculate the total Sum = 779 and K = 3. So, 779 is divisible by 3.

首先，我们计算总和= 779和K = 3 。 因此， 779被3整除。

Then we will choose any of the value from starting and start our backtracking algorithm according to that and find the subsets with equal sum,

然后，我们将从开始选择任何值，然后根据该值开始我们的回溯算法，然后找到总和相等的子集，

{85,21,23,70,85}    {28,59,31,93,73}    {29,51,25,97,82}

C++ implementation:

C ++实现：

#include 
    
     using namespace std;bool is_partiable(int* arr, int n, int sum, int curr_sum, bool* visited, int pos){
       if (curr_sum == sum) {
           return true;    }    if (pos >= n || pos < 0) {
           return false;    }    for (int i = pos; i >= 0; i--) {
           //take the elements those are not visited        if (!visited[i]) {
               visited[i] = true;            if (curr_sum + arr[i] <= sum && is_partiable(arr, n, sum, curr_sum + arr[i], visited, i - 1)) {
                   return true;            }            visited[i] = false;        }    }    return false;}bool isKPartitionPossible(int A[], int N, int k){
       int sum = 0;    for (int i = 0; i < N; i++) {
           sum += A[i];    }    if (sum % k != 0)        return false;    sum = sum / k;    bool visited[N];    memset(visited, false, sizeof(visited));    for (int i = 0; i < k - 1; i++) {
           int curr_sum = 0;        int pos = N - 1;        if (!is_partiable(A, N, sum, curr_sum, visited, pos))            return false;    }    return true;}int main(){
       int t;    cout << "Test Case : ";    cin >> t;    while (t--) {
           int n;        cout << "Enter the value of n : ";        cin >> n;        int arr[n];        cout << "Enter the numbers : ";        for (int i = 0; i < n; i++) {
               cin >> arr[i];        }        int k;        cout << "Enter the value of K : ";        cin >> k;        if (isKPartitionPossible(arr, n, k)) {
               cout << "Partition possible" << endl;        }        else {
               cout << "Partition is not possible" << endl;        }    }    return 0;}
    

Output

输出量

Test Case : 2Enter the value of n : 29Enter the numbers : 71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65 29 42 51 94 1 35 65 25 15 88 57 44Enter the value of K : 2Partition is not possibleEnter the value of n : 15Enter the numbers : 29 28 51 85 59 21 25 23 70 97 82 31 85 93 73Enter the value of K : 3Partition possible

翻译自:

奇数 横竖斜总和相等