leetcode - 순열과 조합

조합(Combination)

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

문제풀이(backtracking)

import java.util.*;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> answer = new ArrayList<>();
        backtracking(n, k, new boolean[n], 0, answer);
        return answer;
    }
    
    public void backtracking (int n, int k, boolean[] visited, int start, List<List<Integer>> answer) {
        if(k == 0) {
            List<Integer> cases = new ArrayList<Integer>();
            for(int i = 0; i < visited.length; i++) {
                if(visited[i])
                    cases.add(i + 1);
            }
            answer.add(cases);
        } else {
            for(int i = start; i < n; i++) {
                visited[i] = true;
                backtracking(n, k - 1, visited, i + 1, answer);
                visited[i] = false;
            }   
        }
    }
}

순열(permutation)

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

문제풀이(backtracking)

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        // nums.length 길이의 순열만 출력
        backtracking(nums, new boolean[nums.length], 0, nums.length, nums.length, answer, new int[nums.length]);
        return answer;
    }
    
    public void backtracking (int[] nums, boolean[] visited, int depth, int len, int n, List<List<Integer>> answer, 
                             int[] curPerm) {
        if(depth == len) {
            List<Integer> perm = new ArrayList<>();
            for(int i = 0; i < curPerm.length; i++) {
                perm.add(curPerm[i]);
            }
            answer.add(perm);
        } else {
            for(int i = 0; i < n; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    curPerm[depth] = nums[i]; 
                    backtracking(nums, visited, depth + 1, len, n, answer, curPerm);
                    visited[i] = false;
                }
            }
        }
    }
}