순열, 조합 구현

순열, 조합을 dfs 백트래킹으로 구현

def permutation(items, selected, visit, count):
    if len(selected) == count:
        print(selected)
        return

    for i in range(len(items)):
        # 고르는 경우
        if visit[i]:
            continue

        selected.append(items[i])
        visit[i] = True
        permutation(items, selected, visit, count)
        selected.pop()
        visit[i] = False


def combination(items, selected, visit, count, index):
    # print(selected, visit, index)
    if len(selected) == count:
        print(selected)
        return

    for i in range(index, len(items)):
        # 고르는 경우
        if visit[i]:
            continue

        selected.append(items[i])
        visit[i] = True
        combination(items, selected, visit, count, i+1)
        selected.pop()
        visit[i] = False


items = [1, 2, 3, 4]
visit = [False for _ in range(len(items))]
# permutation(items, [], visit, 3)
combination(items, [], visit, 3, 0)

public class Solution {

    private int n,r;
    boolean[] visit;
    private int[] items, selected;

    public void printAllPermutation(int[] items, int count){
        this.items = items;
        this.n = items.length;
        this.r = count;
        this.selected = new int[r];
        this.visit = new boolean[n];

        permutation(0);
    }

    public void printAllCombination(int[] items, int count){
        this.items = items;
        this.n = items.length;
        this.r = count;
        this.selected = new int[r];
        this.visit = new boolean[n];

        combination(0,0);
    }

    private void permutation(int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(selected));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                selected[depth] = items[i];
                permutation(depth + 1);
                visit[i] = false;
            }
        }
    }

    private void combination(int depth,int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(selected));
            return;
        }

        for(int i=start;i<n;i++){
            if(!visit[i]){
                visit[i] = true;
                selected[depth] = items[i];
                combination(depth+1,i+1);
                visit[i] = false;
            }
        }
    }

    @Test
    void test() {
        int[] arr = new int[]{0,1,2,3,4};
        printAllPermutation(arr,3);
        System.out.println("-------------");
        printAllCombination(arr,3);
    }
}