코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

https://www.acmicpc.net/problem/1182

[나의 풀이]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    // static 변수 초기화
    // ans (S에 해당하는 갯수)
    static int ans = 0;

    static void print(int[] arr, boolean[] visited, int S) {

        int check_S = 0;

        for(int i = 0; i < arr.length; i++) {

            // 조합을 구한뒤 check_S에 더해서 S인지 확인
            if(visited[i] == true){
                check_S += arr[i];
            }
        }

        // 합이 S이면 ans에 +1
        if (check_S == S){
            ans += 1;
        }
        
        return ;
    }

    // combination 함수 정의
    static void comb1(int[] arr, boolean[] visited, int start, int r, int S) {
        if(r == 0) {

            print(arr, visited,S);

            return;

        } else {

            for(int i = start; i < arr.length; i++) {
                visited[i] = true;
                comb1(arr, visited, i + 1, r - 1,S);
                visited[i] = false;


            }
        }
    }


    public static void main(String[] args) throws IOException {
        
        // 입력값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int  N = Integer.parseInt(st.nextToken());
        int [] arr = new int [N];
        int  S = Integer.parseInt(st.nextToken());

        st  = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 부분수열 최소 1개부터 최대 5개까지 (1 <= r <= 5)

        boolean [] visited = new boolean [arr.length];
        int start = 0;

        for (int r = 1; r<arr.length+1; r++){
            comb1(arr, visited, start, r, S);
        }
        
        // 최종답 출력
        System.out.print(ans);

    }
}

[팀원의 풀이1]

브르투포스 알고리즘 (combination 활용)

# coding = utf-8

import sys
input = sys.stdin.readline
from itertools import combinations

n, s = map(int, input().split())
ls = list(map(int, input().split()))

res = 0
for i in range(1, n+1) :
    for choice in combinations(ls, i) :
        print(choice)
        if sum(choice) == s:
            res += 1

print(res)

[팀원의 풀이2]

백트레킹 알고리즘 (재귀함수)

# coding = utf-8

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
ls = list(map(int, input().split()))

ans = 0
def backtracking(idx, res):
    global ans

    if idx >= n:
        return

    res += ls[idx]
    if res == s:
        ans += 1
    backtracking(idx+1, res)
    backtracking(idx+1, res-ls[idx])

backtracking(0, 0)
print(ans)

브루트포스 or 백트레킹으로 해결 가능한 문제입니다. python으로 활용한다면 간단히 combination 함수로 부분집합을 구할 수 있지만 java 기준으로는 직접 조합을 구현해야했습니다. 그리하여 구글링!!!을 통해서

출처 :
https://minhamina.tistory.com/38

조합 알고리즘을 파악했고 문제에 적용시켰습니다! 문제 정의하는 것 자체는 어렵지 않았습니다. 하지만 백트레킹, 재귀함수 각 두가지 방법으로 combination 구현하는 코드들를 이해하는데 조금 시간을 소비했습니다.😰😰😰 그래도 최근에는 다른 사람의 코드를 자주 찾아보고 이해하는 힘을 기르다보니 스스로 실력이 느는게 느껴집니다! 화이팅!🐥🐥🐥