부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2

내가 약한 완전탐색 + DFS유형

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


using namespace std;
int K;
int N;
int ianswer;
int arr[21] = { 0, };
bool chk[21] = { false, };

void dfs(int idx,int isum)
{
    if (isum == K)
    {
        ianswer++;
        return;
    }

    if (isum > K)   return;

    for (int i = idx; i < N; i++)
    {
     
        dfs(i+1,isum + arr[i]);
        
    }
}

int main() {

    int test_case;  cin >> test_case;

    for (int m = 1; m <= test_case; m++) 
    {

        for (int i = 0; i < 21; i++)
        {
            arr[i] = 0;
        }
        cin >> N;
        cin >> K;

        for (int i = 0; i < N; i++)
        {
            cin >> arr[i];
        }

        dfs(0,0);


        cout << "#" << m << " " << ianswer << endl;
        ianswer = 0;
    }

    //종료
    return 0;
}

이문제를 보고 합이 K라는 경우의 수를 구하기 위해
1. DFS를 쓴다는 것을 떠올리는것과,
2. DFS내부에서 이 문제에선 chk[]검토없이
for(int i = idx; i<N; i++)
{
func(i+1, sum+arr[i];
}
을 하는게 중요하다. 중복처리 자동으로 없애고(자신보다 뒤에있는 원소 전달하기 위해 i+1을 넘기는게 중요함)
이걸 이해해야한다.

[중요]
그리고 밑은 내 풀이인데, 이렇게하면 답이 8이나와 틀린다.
왜 위에처럼 풀이를 해야하냐면, 1 1 0 0 에서 index 0 -> 1 갈때 1 1 로 가고(chk해제함)
index 1 -> 0으로 갈때 실제로 1 1 0 0 같은건데 (for문에서 i가 0에서 1로변했음) 방문조건이 다르므로 답에 한번 더들어가게된다.
이해하자. DFS 할때도 무조건 Chk함수로만 가는게 아닌 경우도 있다. (답에서 구분을 못하는 경우 Chk가 아닌 for안의 변수로 조절해야함)

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


using namespace std;
int K;
int N;
int ianswer;
int arr[21] = { 0, };
bool chk[21] = { false, };
vector<string> chkVec;


void dfs(int isum)
{
    if (isum == K)
    {
        string sTemp; 
        for (int i = 0; i < 4; i++)
        {
            if (chk[i] == true)
            {
                sTemp += "1/";
            }
            else
            {
                sTemp += "0/";
            }
        }
        chkVec.push_back(sTemp);
        ianswer++;
        return;
    }

    if (isum > K)   return;

    for (int i = 0; i < N; i++)
    {
        if (chk[i] == 0)
        {
            chk[i] = 1; 
            dfs(isum + arr[i]);
            chk[i] = 0;
        }
    }
}

int main() {

   

    for (int m = 1; m <= 1; m++)
    {

        for (int i = 0; i < 21; i++)
        {
            arr[i] = 0;
        }
        cin >> N;
        cin >> K;

        for (int i = 0; i < N; i++)
        {
            cin >> arr[i];
        }

        dfs(0);


        cout << "#" << m << " " << ianswer << endl;
        ianswer = 0;
    }

    //종료
    return 0;
}