[C++]プログラマ:ターゲット番号
#include <string>
#include <vector>
using namespace std;
bool visited[21] = {0}; // 방문 여부
int Numbers[21] = {0}; // 숫자 저장
int arrSize;
int Target;
int cnt = 0;
bool flag = true; // 모두 탐색 되었는지 검사
//백트래킹
void DFS(int idx, int tmp){
if(tmp == Target && idx == arrSize){
for(int j = 0; j < arrSize; j++){
if(visited[j] == 0){
flag = false;
}
}
if(flag){
cnt++;
} else {
flag = true; // 초기화
}
return;
}
for(int i = idx; i < arrSize; i++){
visited[i] = 1;
DFS(i+1, tmp - Numbers[i]);
DFS(i+1, tmp + Numbers[i]);
visited[i] = 0;
}
}
int solution(vector<int> numbers, int target) {
int answer = 0;
for(int i = 0; i < numbers.size(); i++){
Numbers[i] = numbers[i]; // 벡터 복사
}
arrSize = numbers.size();
Target = target;
DFS(0, 0); // 첫 숫자부터 값 0부터 시작
answer = cnt;
return answer;
}
インターネットを見なくても簡単にバックグラウンド追跡ができるようになりました.大神を踊るプログラマーの環境で鼻カチューシャをすることがあるので解いていますね気まずいですね
特に、すべての数がparameterとして指定されている場合、グローバル変数として使用するには、別途再割り当てが必要です.
backtrackingを使用して、すべての場合に数値を検索し、値を求めます.0から、数値-または+を1つずつ探索します.すべての数値が検出された場合(-または+).結果値がtarget値に等しい場合は、-、+をtarget値に組み合わせます.backtrackingの場合、結果値が重複することは絶対にありません.したがって、cnt++はすべてアクセスした場合にのみ計算されます.
Reference
この問題について([C++]プログラマ:ターゲット番号), 我々は、より多くの情報をここで見つけました https://velog.io/@lamknh/C-프로그래머스-타겟-넘버テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol