순열, 조합, 부분집합 템플릿

순열 permutation

n, r이 주어졌을 때

import java.util.*;

public class PermutationGenerator {

    public static List<List<Integer>> permute(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];  // 1부터 n까지 숫자를 사용하기 위해 크기를 n+1로 설정
        backtrack(n, r, new ArrayList<>(), visited, ans);
        return ans;
    }

    private static void backtrack(int n, int r, List<Integer> curr, boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));  // 정답 저장
            return;
        }

        for (int i = 1; i <= n; i++) {  // 1부터 n까지 숫자 직접 사용
            if (!visited[i]) {  // 방문하지 않은 숫자만 선택
                curr.add(i);
                visited[i] = true;
                backtrack(n, r, curr, visited, ans);
                curr.remove(curr.size() - 1);  // Backtracking: 원래 상태로 되돌리기
                visited[i] = false;  // 방문 체크 해제
            }
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int r = 2;
        List<List<Integer>> result = permute(n, r);
        for (List<Integer> p : result) {
            System.out.println(p);
        }
    }
}

nums, r이 주어질 때

import java.util.*;

public class PermutationWithArray {

    public static List<List<Integer>> permute(int[] nums, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(r, new ArrayList<>(), nums, visited, ans);
        return ans;
    }

    private static void backtrack(int r, List<Integer> curr, int[] nums, boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                curr.add(nums[i]);
                visited[i] = true;
                backtrack(r, curr, nums, visited, ans);
                curr.remove(curr.size() - 1);
                visited[i] = false; // Backtracking: 원래 상태로 되돌리기
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int r = 2;
        List<List<Integer>> result = permute(nums, r);
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }
}

 

조합 combination

n, r이 주어졌을 때

import java.util.*;

public class Combination {

    public static List<List<Integer>> combine(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, r, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int n, int r, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr)); // 정답 저장
            return;
        }

        for (int i = start; i <= n; i++) { // 중복 방지를 위해 `start`부터 탐색
            curr.add(i);
            backtrack(i + 1, curr, n, r, ans); // 다음 숫자는 현재 숫자보다 커야 함
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int r = 2;
        List<List<Integer>> result = combine(n, r);
        for (List<Integer> comb : result) {
            System.out.println(comb);
        }
    }
}

nums, r이 주어질 때

import java.util.*;

public class Combination {

    public static List<List<Integer>> combine(int[] nums, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, r, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int[] nums, int r, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr)); // 정답 저장
            return;
        }

        for (int i = start; i < nums.length; i++) { // 중복 방지를 위해 `start`부터 탐색
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums, r, ans); // 다음 숫자는 현재 숫자보다 커야 함
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 40};
        int r = 2;
        List<List<Integer>> result = combine(nums, r);
        for (List<Integer> comb : result) {
            System.out.println(comb);
        }
    }
}

부분집합 subset

n, r이 주어졌을 때

import java.util.*;

public class Subsets {

    public static List<List<Integer>> subsets(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int n, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(curr)); // 현재 부분집합을 저장

        for (int i = start; i <= n; i++) { // 숫자를 하나씩 추가하며 탐색
            curr.add(i);
            backtrack(i + 1, curr, n, ans); // 다음 숫자를 선택
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int n = 3;
        List<List<Integer>> result = subsets(n);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

nums, r이 주어질 때

import java.util.*;

public class SubsetsWithArray {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int[] nums, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(curr)); // 현재 부분집합을 저장

        for (int i = start; i < nums.length; i++) { // 숫자를 하나씩 추가하며 탐색
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums, ans); // 다음 숫자를 선택
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30};
        List<List<Integer>> result = subsets(nums);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}