C++에서 부분 집합의 요소 합을 N으로 나눌 수 있도록 N 정수 배열에서 비어 있지 않은 부분 집합을 찾습니다.

n개의 숫자 배열이 있다고 가정합니다. 부분 집합의 요소 합이 n으로 나눌 수 있도록 비어 있지 않은 부분 집합을 찾아야 합니다. 따라서 원래 배열이 있는 경우 해당 크기와 요소 인덱스를 사용하여 이러한 하위 집합을 출력해야 합니다.

따라서 입력이 [3, 2, 7, 1, 9]와 같으면 출력은 [2], [1 2]가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 지도 my_map 정의
• 추가:=0
• 초기화 i의 경우:=0, i
• 추가 :=(추가 + arr[i]) 모드 N
• 추가가 0과 같으면 -
  • i + 1 인쇄
  • j 초기화의 경우 :=0, j <=i일 때 업데이트(j를 1만큼 증가), 수행 -
    • j + 1 인쇄
  • 반환
• my_map에 추가하면 -
  • 인쇄(i - my_map[추가])
  • j 초기화의 경우:=my_map[add] + 1, j <=i일 때 업데이트(j를 1만큼 증가), −
    • j + 1 인쇄
  • 반환
• 그렇지 않으면
  • my_map[추가] :=나

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void subset_find(int arr[], int N) {
   unordered_map<int, int> my_map;
   int add = 0;
   for (int i = 0; i < N; i++) {
      add = (add + arr[i]) % N;
      if (add == 0) {
         cout << i + 1 << endl;
         for (int j = 0; j <= i; j++)
            cout << j + 1 << " ";
         return;
      }
      if (my_map.find(add) != my_map.end()) {
         cout << (i - my_map[add]) << endl;
         for (int j = my_map[add] + 1; j <= i; j++)
            cout << j + 1 << " ";
         return;
      }
      else
         my_map[add] = i;
   }
}
int main() {
   int arr[] = {3, 2, 7, 1, 9};
   int N = sizeof(arr) / sizeof(arr[0]);
   subset_find(arr, N);
}

입력

{3, 2, 7, 1, 9}

출력

2
1 2