728x90

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
Code :
var permuteUnique = function(nums) {
// 결과를 저장할 배열을 선언합니다.
const result = [];
// 배열을 정렬합니다.
nums.sort((a, b) => a - b);
// 백트래킹 함수를 정의합니다.
const backtrack = (current, remaining) => {
// 재귀 호출 기저 조건: 남은 요소가 없는 경우 현재 배열을 결과에 추가하고 종료합니다.
if (remaining.length === 0) {
result.push(current.slice());
return;
}
// 중복된 요소를 건너뛰며 각 요소에 대해 재귀적으로 백트래킹을 수행합니다.
for (let i = 0; i < remaining.length; i++) {
if (i > 0 && remaining[i] === remaining[i - 1]) {
continue;
}
current.push(remaining[i]);
backtrack(current, remaining.slice(0, i).concat(remaining.slice(i + 1)));
current.pop();
}
};
// 백트래킹 함수를 초기 호출합니다.
backtrack([], nums);
// 결과 배열을 반환합니다.
return result;
};
Solutions Code :
var permuteUnique = function(nums) {
// 결과를 저장할 배열을 초기화합니다.
const res = [];
// 각 요소의 출현 빈도를 저장할 객체를 초기화합니다.
const countMap = {};
// nums 배열을 순회하면서 각 요소의 출현 빈도를 저장합니다.
for (let i = 0; i < nums.length; i++) {
const curVal = nums[i];
// 출현 빈도가 없는 경우 1로 초기화하고, 있는 경우 1을 더합니다.
if (!countMap[curVal]) {
countMap[curVal] = 1;
} else {
countMap[curVal] += 1;
}
}
// 깊이 우선 탐색 함수를 호출합니다.
dfs(nums, [], countMap, res);
// 결과 배열을 반환합니다.
return res;
};
// 깊이 우선 탐색 함수를 정의합니다.
function dfs(nums, path, countMap, res) {
// 기저 조건: 경로의 길이가 nums의 길이와 같아지면 결과 배열에 추가합니다.
if (path.length === nums.length) {
return res.push([...path]);
}
// countMap을 순회하면서 각 요소의 출현 빈도를 확인하고 백트래킹을 수행합니다.
for (const num in countMap) {
const numCount = countMap[num];
// 출현 빈도가 0이면 건너뜁니다.
if (numCount === 0) continue;
// 요소를 path에 추가하고 출현 빈도를 1 감소시킵니다.
path.push(num);
countMap[num] -= 1;
// 재귀 호출을 통해 백트래킹을 수행합니다.
dfs(nums, path, countMap, res);
// 요소를 path에서 제거하고 출현 빈도를 1 증가시킵니다.
path.pop();
countMap[num] += 1;
}
}
출처 : https://leetcode.com/problemset/all/
Problems - LeetCode
Boost your coding interview skills and confidence by practicing real interview questions with LeetCode. Our platform offers a range of essential problems for practice, as well as the latest questions being asked by top-tier companies.
leetcode.com
728x90
'LeetCode' 카테고리의 다른 글
[LeetCode] 49. Group Anagrams (0) | 2023.11.10 |
---|---|
[LeetCode] 48. Rotate Image (2) | 2023.11.10 |
[LeetCode] 46. Permutations (0) | 2023.11.09 |
[LeetCode] 45. Jump Game II (2) | 2023.11.09 |
[LeetCode] 44. Wildcard Matching (0) | 2023.11.09 |