[알고리즘] c++ cpp 두 개 뽑아서 더하기

포인트

1. 조합을 구현을 할 수 있는가? (How to generate code about combination)

조합을 만들 수 있는 방법은 많다. (재귀, 반복문)

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

반복문

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;


    for(int i=0; i<numbers.size(); i++){
        for (int j = i+1; j < numbers.size(); ++j) {
                answer.push_back(numbers[i]+numbers[j]);
        }
    }
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    

    return answer;
}

재귀 (굳이 재귀를 사용해서 조합을 구현을 할 필요는 없습니다. )

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int sel[2];
vector<int> answer;

void go(int index, int cnt, vector<int> vc, vector<int> visited) {
    if (cnt == 2) {
        int a = 0;
        for (int i = 0; i < 2; i++) {
            a += sel[i];
        }
        answer.push_back(a);
        return;
    }

    for (int i = index; i < vc.size(); i++) {
        if (visited[i]) continue;
        sel[cnt] = vc[i];
        visited[i] = 1;
        go( i+ 1, cnt + 1, vc, visited);
        visited[i] = 0;
    }
}


vector<int> solution(vector<int> numbers) {
    sort(numbers.begin(), numbers.end());
    vector<int> visited(numbers.size());

    go(0, 0, numbers, visited);
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());

    return answer;
}