总和可被m整除的子集


难度级别
经常问 弓箭 思科 指令 Expedia的 Myntra PayU
排列 动态编程

问题陈述

问题“总和可被m整除的子集”指出给您一个非负整数和整数m的数组。 现在,您需要查找是否存在一个子集,其总和可被m整除。 那就是当我们采用m的模式时,子集的总和应该给出0。

使用案列

总和可被m整除的子集

array = {1, 2, 4}
m = 3
True

说明

值{1,2}的子集总和为3。 {2,4}的总和也得出6,结果也可以被3整除。因此答案是正确的。

途径

因此,我们也遇到了类似的问题,即检查 子集的总和等于目标总和。 但是这里不检查子集和是否等于给定的和,但是我们需要检查子集和是否可被m整除。 因此我们可以重新构造问题,因为我们需要找到是否有一个子集具有sum = m,2m,3m等。如果该子集的总和等于任何给定值。 我们返回true,否则返回false。

所以,不要这样想。 我们继续求和的模,如果我们以某种方式得到0,我们肯定存在一个子集,其总和可以被m整除。 但是在此之前,我们需要关心一些事情。 如果元素数量n> = m(针对其mod的数量)。 然后,由于鸽洞原理,答案总是存在的。 我们只需要处理0和m-1之和为n <= m的情况。

因此,此方法背后的整体思想是,我们有一些子集的总和= j,然后我们可以创建新子集的总和=(j + current_element)%m。 这就是我们要填补我们的方式 动态编程 表。

代码

子集的C ++代码,其和可被m整除

#include<bits/stdc++.h>
using namespace std;

bool findSubsetDivisibleByM(int arr[], int n, int m)
{
  // because of piegonhole principle
  if (n > m)
    return true;

  // this will work as dp array for all elements until the last element
  bool dp[m]; memset(dp, false, m);

  for (int i=0; i<n; i++)
  {
    // this will work as our current dp array
    bool tmp[m]; memset(tmp,false,m);

    // we will add the current element to all possible subset sum
    // until now and then take the mod of the sum and will keep
    // on filling the current dp array(tmp)
    for (int j=0; j<m; j++)
    {
      // if the dp table until the last element has subset sum = j
      if (dp[j] == true)
      {
        if (dp[(j+arr[i]) % m] == false)
          // fill the current dp table(tmp array)
          tmp[(j+arr[i]) % m] = true;
      }
    }

    // now just fill the original dp array
    for (int j=0; j<m; j++)
      if (tmp[j] == true)
        dp[j] = true;
    // fill the dp array considering you have subset made of only current element
    dp[arr[i]%m] = true;
  }

  return dp[0];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // Number which should divide the subset
  int m;cin>>m;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  bool can = findSubsetDivisibleByM(a, n, m);
  if(can == true)
    cout<<"There exists a subset having sum divisible by m";
  else
    cout<<"There does not exist any subset having sum divisible by m";
}
3 3 
1 2 4
There exists a subset having sum divisible by m

子集的Java代码,其总和可被m整除

import java.util.*;
class Main{
  
  	static boolean findSubsetDivisibleByM(int arr[], int n, int m)
  {
    // because of piegonhole principle
    if (n > m)
      return true;

    // this will work as dp array for all elements until the last element
    boolean dp[] = new boolean [m];
    for(int i=0;i<m;i++)
      dp[i] = false;

    for (int i=0;i<n; i++)
    {
      // this will work as our current dp array
      boolean tmp[] = new boolean[m];
      for(int j=0;j<m;j++)
        tmp[j] = false;
      // we will add the current element to all possible subset sum
      // until now and then take the mod of the sum and will keep
      // on filling the current dp array(tmp)
      for (int j=0; j<m; j++)
      {
        // if the dp table until the last element has subset sum = j
        if (dp[j] == true)
        {
          if (dp[(j+arr[i]) % m] == false)
            // fill the current dp table(tmp array)
            tmp[(j+arr[i]) % m] = true;
        }
      }

      // now just fill the original dp array
      for (int j=0; j<m; j++)
        if (tmp[j] == true)
          dp[j] = true;
      // fill the dp array considering you have subset made of only current element
      dp[arr[i]%m] = true;
    }

    return dp[0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // Number of elements
    int n = sc.nextInt();
    int m = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    boolean can = findSubsetDivisibleByM(a, n, m);
    if(can == true)
      System.out.println("There exists a subset having sum divisible by m");
    else
      System.out.println("There does not exist any subset having sum divisible by m");
  	}
}
3 3
1 2 4
There exists a subset having sum divisible by m

复杂度分析

时间复杂度

O(M ^ 2),因为我们仅在n <= m时才需要解决问题。 因此,n的上限为m。 因此,时间复杂度是多项式。

空间复杂度

O(M), 因为dp阵列所需的空间是线性的。 仅需要空间来存储dp表,因此空间复杂度是线性的。