Algorithm/PTUStudy

16주차. 그래프(순열)

지구우중 2023. 5. 23. 15:41

34. 순열

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

 

Permutations - LeetCode

Can you solve this real interview question? Permutations - 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],

leetcode.com

📌문제

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.


- 예제1
  📝입력

digits = "23"



  💻출력

["ad","ae","af","bd","be","bf","cd","ce","cf"]


📌풀이

1ms, 43.3mb

class Solution {
     public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permutation(result, nums, new boolean[nums.length], 0, nums.length, new Integer[nums.length]);
        return result;
    }

    public void permutation(List<List<Integer>> result, int[] nums, boolean[] visited, int depth, int r, Integer[] make) {
        if (depth == r) {
            result.add(Arrays.asList(make.clone()));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                make[depth] = nums[i];
                permutation(result, nums, visited, depth + 1, r, make);
                visited[i] = false;
            }
        }
    }
}

예전에 순열, 조합문제를 주구장창 풀었던 결과 어렵지 않게 풀었음..