[프로그래머스] 연속 부분 수열 합의 개수

배열이 주어졌을 때 가능한 부분수열의 합이 몇 개인지 구하는 문제

1부터 배열크기만큼의 부분수열을 모두 구하고 방문 검사를 통해 총 개수를 구하면 된다.

https://school.programmers.co.kr/learn/courses/30/lessons/131701

cpp code

#include <vector>

using namespace std;

bool visited[1'000'001];

int solution(vector<int> elements) {
    for (int i=1;i<=elements.size();i++) {
        int sum = 0;
        for (int j=0;j<i;j++) {
            sum += elements[j];
        }
        visited[sum] = true;
        for (int j=i;j<elements.size()+i-1;j++) {
            sum += elements[j % elements.size()];
            sum -= elements[j - i];
            visited[sum] = true;
        }
    }
    int ans = 0;
    for (int i=0;i<=1'000'000; i++) {
        ans += visited[i];
    }
    return ans;
}