Permutations

🔗 문제 링크

https://leetcode.com/problems/permutations/

🔍 문제 설명

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

⚠️ 제한사항

• $1 <= nums.length <= 6$

• $-10 <= nums[i] <= 10$

• All the integers of nums are unique.

🗝 풀이 (언어 : Java)

순열의 경우의 수들을 만드는 문제이다. DFS로 원소를 계속 채우고 길이가 다차면 정답에 넣고 부분 리스트의 원소를 끝에서 제거해주면서 다시 다음 숫자로 채우는 알고리즘이다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private void dfs(List<List<Integer>> answer, List<Integer> oneCase, int[] nums, boolean[] used) {
        // 한개의 경우의 수가 완성되어 추가
        // 해당 케이스 리스트는 새로운 리스트에 담아서 넣기, 뒤의 원소 지우고 재사용되기 때문
        if (oneCase.size() == nums.length) {
            answer.add(new ArrayList<>(oneCase));
            return;
        }
        // 조합 만들기
        for (int i = 0; i < nums.length; i++) {
            // 해당 원소가 이미 앞쪽에 들어있으면 스킵
            if (used[i])
                continue;
            used[i] = true;
            oneCase.add(nums[i]);
            // 다음 차례 원소 찾아 넣기
            dfs(answer, oneCase, nums, used);
            // n개 모두 채워서 정답처리했으면 끝 원소 제거해서 다른 원소 넣어 반복
            used[i] = false;
            oneCase.remove(oneCase.size()-1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        // 해당 순서의 원소 사용했는지 체크하는 배열
        boolean[] used = new boolean[nums.length];
        dfs(answer, new ArrayList<>(), nums, used);
        return answer;
    }
}