알고리즘-완전탐색

완전탐색:모든 경우의 수를 모두 계산하여 출력값을 구함
크게 4가지로 나뉠수있다.
1.중복을 허용, 순서있게 나열 (BOJ 15651)

import java.util.*;
import java.io.*;
//1부터 n까지 골라서 m개를 고른 수열
public class bf_1 {
   static StringBuilder sb= new StringBuilder();

   static void input() { //입력 클래스
       FastReader fr = new FastReader();
       n = fr.nextInt();
       m = fr.nextInt();
       selected = new int[m + 1]; //배열 생성
   }
    public static int n,m;
    public static int[] selected;
       static void rec_func(int k) {
           if(k==m+1){
               for(int i=1;i<=m;i++) sb.append(selected[i]).append(' ');
               sb.append('\n');
           } else {
               for(int cand=1;cand<=n;cand++){
                   selected[k]=cand;
                   rec_func(k+1);
                   selected[k]=0;
               }
           }
       }

    public static void main(String[] args) {
        input();
        rec_func(1); //
        System.out.println(sb.toString());
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

2.중복 없이,순서대로 (BOJ 15649)

import java.util.*;
import java.io.*;
//1부터 n까지 골라서 m개를 고른 수열
public class bf_2 {
    static StringBuilder sb = new StringBuilder();

    static void input() { //입력 클래스
        FastReader fr = new FastReader();
        n = fr.nextInt();
        m = fr.nextInt();
        selected = new int[m + 1]; //배열 생성
    }

    public static int n, m;
    public static int[] selected;
    public static int[] used;

    static void rec_func(int k) {
        if (k == m + 1) {
            for (int i = 1; i <=m; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = 1; cand <= n; cand++) {
                if(cand==1) continue; //값을 사용 했으면 cotinue
                selected[k]=cand;  used[cand]=1;
                rec_func(k+1);
                selected[k]=0;  used[cand]=0;
            }
        }
    }

    public static void main(String[] args) {
        input();
        rec_func(1); //재귀함수
        System.out.println(sb.toString());
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

3.중복허용,(BOJ 15652)

import java.util.*;
import java.io.*;
//1부터 n까지 골라서 m개를 고른 수열
public class bf_3 {
    static StringBuilder sb= new StringBuilder();

    static void input() { //입력 클래스
        FastReader fr = new FastReader();
        n = fr.nextInt();
        m = fr.nextInt();
        selected = new int[m + 1]; //배열 생성
    }
    public static int n,m;
    public static int[] selected;
    static void rec_func(int k) {
        if(k==m+1){
            for(int i=1;i<=m;i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
           int start=selected[k-1];
           if(start==0) start=1;
           for(int cand=start;cand<=n;cand++){
               selected[k]=cand;
               rec_func(k+1);
               selected[k]=0;
           }
        }
    }
    public static void main(String[] args) {
        input();
        rec_func(1); //재귀함수
        System.out.println(sb.toString());
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.중복없이

import java.util.*;
import java.io.*;
//1부터 n까지 골라서 m개를 고른 수열
public class bf_4 {
    static StringBuilder sb= new StringBuilder();

    static void input() { //입력 클래스
        FastReader fr = new FastReader();
        n = fr.nextInt();
        m = fr.nextInt();
        selected = new int[m + 1]; //배열 생성
    }
    public static int n,m;
    public static int[] selected;
    static void rec_func(int k) {
        if(k==m+1){
            for(int i=1;i<=m;i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for(int cand=selected[k-1]+1;cand<=n;cand++){
                selected[k]=cand;
                rec_func(k+1);
                selected[k]=0;
            }
        }
    }

    public static void main(String[] args) {
        input();
        rec_func(1); //재귀함수
        System.out.println(sb.toString());
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

import java.util.Scanner;

public class Bf6 {

    static int n,s,ans;
    static int[] nums;

    static void input(){
        Scanner sc= new Scanner(System.in);
        n=sc.nextInt();
        s=sc.nextInt();
        nums= new int[n+1];
        for(int i=1; i<=n; i++) nums[i]= sc.nextInt();
    }
    static void pro(int k, int value){
        if(k==n+1){
            if(value==s) ans++;
        }else {
            pro(k+1,value+nums[k]);
            pro(k+1,value);
        }
    }

    public static void main(String[] args) {
        input();
        pro(1,0);
        if(s==0){
            ans--;
        }
        System.out.println(ans);
    }
}