시도1

  public static void solve(int idx){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            list.remove(list.size()-1);
        }
      
        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve(i+1);
            }
        }
    }

• idx=1일때를 생각해보면
• idx=1일때 결과가 1 하나만 출력이돼야한다. 근데 1일떄 1,2,3모두 출력된다.
• 이런식이면 idx=2일때도 결과가 출력된다는얘기다. 그러므로 이 코드는 틀렸다.
• 그리고 remove의 위치도 문제가된다.
• size=m일때만 제거를 하는것이니 1로출발해서 두개를 출력해야하면 1로시작하는것만나온다

시도2

 public static void solve(int idx){
        //1이추가된다
        list.add(idx);
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();

        }
        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                solve(i+1);
                list.remove(list.size()-1);
            }
        }
    }

• 1 2 출력을 하고 나와서 2 제거한다
• 그다음 반복에서 1 3 출렫하고 3제거한다
• 반복끝
• 재귀함수 첫번째에 넣게되면. 재귀함수 호출되는 순간만 add하겠다는것이다.
  함수내부의 재귀함수를 호출하는 부분은 for문 하나니까 그갯수만 나오기때문에
  오답이 나올것이다. 이럴땐 for문안에 add문을 넣어주면 여러개를 출력하게될수있다

시도3

public static void solve(int idx){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            return;

        }
        for(int i=idx;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve(i);
                list.remove(list.size()-1);
            }
        }
    }

• for문의계속증가하고있는 인덱스인 i를넘겨줘서 계속그거부터 시작하게하고있다.
  이렇게된다면 list에 담기는수는 매번 증가하는 수만 추가될것이다.

최종

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.OptionalInt;

public class Main{
    static int n;
    static int m;
    static ArrayList<Integer> list;
    public static void solve(){
        if(list.size()==m){
            for (Integer i:list) System.out.print(i+" ");
            System.out.println();
            return;

        }
        for(int i=1;i<=n;i++){
            if (!list.contains(i)){
                list.add(i);
                solve();
                list.remove(list.size()-1);
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        list = new ArrayList<>();
        solve();

        bw.flush();
        bw.close();
    }
}

• 매번 1부터 검사를해서 내가 리스트에 추가시킨것만 제외시킨다.
• 시간복잡도는 m^n일라나?

5568 카드놓기 (비슷한문제)

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

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static int n;
    static int k;
    static String arr[];
    static ArrayList<String>list = new ArrayList<>();
    static boolean visited[];
    public static void dfs(int idx, String num, int count){

        if(idx > n) return;
        if(count ==k){
            if(!list.contains(num)) list.add(num);
            return;
        }
        for(int i=1;i<arr.length;i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(idx+1, num + arr[i], count+1);
                dfs(idx+1, num, count);
                visited[i] = false;

            }
        }


    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        arr = new String[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = br.readLine();
        }
        dfs(0,"",0);


        bw.write(list.size()+"");
        bw.flush();
        bw.close();

    }
}

dfs(idx+1, num + arr[i], count+1);
dfs(idx+1, num, count);//이줄이 없어도된다

왜냐하면 반복문을 통해 그다음 반복에선 arr[i]을 미포함시키고 진행할것이니깐.