부분수열의 합

https://github.com/Aeopp/Sum_of_partial_sequences

Aeopp/Sum_of_partial_sequences

부분수열의 합이 문제의 제목인데 수열로 풀 필요는 없다 덧셈은 교환법칙과 결합법칙이 성립하기때문에

(정수)원소의 순서가 아무리 바뀌어도 해당 원소들의 합은 동일하기 때문에 모든 조합의 경우의 수를 세고

그 합이 같으면 개수를 더해주는 식으로 풀면됨.

 

함수호출 횟수는 조합의 경우의 수 공식과 동일하다 O(2^N);

 

어짜피 나중에 나만볼거같아서 막썼는데 혹시 댓글달리면 자세히 설명해드림 !!

 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

https://codeup.kr/problem.php?id=3009

부분수열의 합

#include 
#include 
// 정수의 개수
int N_Count;
// 타겟넘버
int Target;
// 정수집합
std::vector Set;
// 집합의 원소들로 만들수 있는 조합의 정수의 합이 Target 과 같다면 SolveResult 를 더한다.
int SolveResult;

// Step
// 1. 정수의 집합을 만듬
// 2. 해당 집합으로 만들수 있는 모든 조합을 구함
// 3. 조합의 원소들의 합이 타겟과 같은 경우의수를 구함
// 4. 재귀로 자기자신을 더한 경우(자기자신을 조합에 포함시킨경우)
// 와 자기자신을 뺀 경우 ( 자기자신을 조합에 포함시키지않은경우) 를 호출하며 개수를 센다.
// 원소개수와 인덱스가 일치하는 경우 재귀를 종료한다. 
void Solve(const int Idx,int Sum)
{
if (Idx >= N_Count)return;
Sum += Set[Idx];
if (Target == Sum)SolveResult++;

/* 함수호출 시간 복잡도는 집합으로 만들수있는 조합의 경우의 수와 일치함.
O(2 ^ N); 여기서 N은 당연히 집합의 원소의 수 */

// 자기자신을 조합에 포함시킨 경우
Solve(Idx + 1, Sum);
// 자기자신을 조합에 포함시키지 않은  경우
Solve(Idx + 1, Sum  - Set[Idx]);
};
int main() {

std:: cin >> N_Count >> Target;

for (int i = 0; i < N_Count; ++i)
{
int temp;
std::cin >> temp;
Set.emplace_back(temp);
};
Solve(0, 0);
std::cout << SolveResult;
return 0;
}