[알고리즘] 타겟 넘버

포인트

• 재귀 함수를 잘 구현을 할 수 있는가?
  • 비트 마스크로도 구현을 할 수 있습니다. 비트 마스크로 생각을 하면 간단히 풀리는 것 같습니다. 
• 재귀는 하면 할수록 신기한 친구네

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

재귀

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

using namespace std;

vector<int> map;
vector<int> sel;
int answer=0;
int tt;
void go(int index, int cnt) {
    if(cnt==map.size()) {
        int sum=0;
        for (auto ele : sel) {
            cout << ele << ' ';
            sum+=ele;
        }
        cout << '\n';

        if (sum == tt) answer+=1;
        return;
    }

    if (index >= map.size ()) return;

    sel.push_back (map[index] * 1);
    go (index + 1, cnt + 1);
    sel.pop_back ();

    sel.push_back (map[index] * -1);
    go (index + 1, cnt + 1);
    sel.pop_back ();
}

int solution (vector<int> numbers, int target) {
    map=numbers;
    tt=target;

    cout << (1 << numbers.size ()) << '\n';
    go (0, 0);

    return answer;
}

int main() {
    cout<<solution ({ 1, 1, 1, 1, 1 }, 3);
}

재귀 함수로 넘어가서 작성을 합니다. (1, -1 을 곱하면서 특정 벡터에 넣어주고 계산을 해줍니다. )

비트 마스크 풀이

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> numbers, int target) {
	int answer=0;

	for(int i=1; i<(1<<numbers.size()); i++) {
		int temp=0;
		for(int k=0; k<numbers.size(); k++) {
			if (i & (1 << k)) temp-=numbers[k];
			else temp+=numbers[k];
		}
		if (temp == target) answer+=1;
	}

	return answer;
}

 

2020 12 04 업데이트

재귀2

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

using namespace std;
vector<int> number;
int t;
int s=0;
void go (int index, int sum) {
    if (index == number.size ()) {
        if (sum == t) s+=1;
    }

    if (index >=number.size ()) return;

    go (index + 1, sum + number[index]);
    go (index + 1, sum - number[index]);
}

int solution (vector<int> numbers, int target) {
    number=numbers;
    t=target;

    go (0, 0);

    return s;
}

int main () {
    cout<<solution ({ 1, 1, 1, 1, 1 }, 3);
}

뭔가 복잡하게 생각을 할 필요가 없었습니다. 

---

2021 03 15

python

재귀를 처음부터 이해할 수 있는 뇌는 감사해야 한다.

answer = 0


def go(index: int, cnt: int, numbers: list, target: int):
    global answer
    if index == len(numbers):
        if cnt == target:
            answer += 1

    if index >= len(numbers):
        return

    go(index + 1, cnt + numbers[index], numbers, target)
    go(index + 1, cnt - numbers[index], numbers, target)


def solution(numbers: list, target: int) -> int:
    global answer
    go(0, 0, numbers, target)
    return answer