[LeetCode] 46. Permutations - 문제풀이

Description

중복되지 않는 값을 가진 배열이 주어졌을때 가능한 순열을 계산하여 반환하는 문제입니다.

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]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Solution 1. BackTracking

public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> result = new ArrayList<>();
    backTracking(result,new ArrayList<Integer>(), nums, nums.length );
    return result;
}

private void backTracking(List<List<Integer>> result, List<Integer> comb, int[] nums,  int depth){

    if(depth == 0 ){
        result.add(new ArrayList<>(comb));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if(comb.contains(nums[i])) continue;
        comb.add(nums[i]);
        backTracking(result,comb, nums, depth-1 );
        comb.remove(comb.size()-1);
    }

}

백트래킹(BackTracking) 알고리즘을 통해 가능한 경우의를 모두 탐색하며 순열을 채워나갑니다. 이미 comb에 포함된 숫자는 더이상 탐색할 필요가 없으므로 스킵하고 계속 재귀호 출하며 depth를 줄여나가면서 숫자를 채워나가고 가능한 경우의수 (depth)의 개수가 채워지면 result에 채워나갑니다.

Reference

Permutations - LeetCode