재귀호출로 배열의 합 검사하기

 

*초기 작성 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> number) {
    int answer = 0;
    int size = number.size();
    
    for(int i = 0; i < size - 2; i++)
    {
        for(int j = i + 1; j < size - 1; j++)
        {
            for(int k = j + 1; k < size; k++)
            {
                if(number[i] + number[j] + number[k] == 0)
                {
                    answer++;
                }
            }
        }
    }
    return answer;
}

 

3중 for문으로 문제를 풀었는데, 다른 사람 풀이를 보니 재귀호출로 조금 더 가독성 있게 풀 수 있다는 것을 확인하고

재귀호출로 구현하였다.

 

 

#include <string>
#include <vector>

using namespace std;

int GetCombinationCnt(vector<int> Number, int Sum, int Count, int Idx)
{
    int Result = 0;
    
    if(Count == 3)
    {
        return Sum == 0;
    }
    
    for(int i = Idx; i < Number.size(); ++i)
    {
        Result += GetCombinationCnt(Number, Sum + Number[i], Count + 1, i + 1);
    }
    
    return Result;
}

int solution(vector<int> Number) {
    return GetCombinationCnt(Number, 0, 0, 0);
}

매개변수로 Sum, Count, Idx 값을 추가로 전달해서, Count가 3이 되었을 때의 Sum의 값이 0인지 확인하고 반환하여 지역변수 Result에 값이 누적된다. 마지막으로 초기 GetCombinationCnt 함수가 호출되었던 시점의 Result 값에 재귀호출하며 누적되었던 Result값이 반환되는 구조이다.