Partition Equal Subset Sum - LeetCode
Can you solve this real interview question? Partition Equal Subset Sum - Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise. Example 1: I
leetcode.com
< 문제 간단설명 >
주어진 nums 배열을 둘의 부분집합으로 나누었을 때, 그 둘의 부분집합 각각의 합이 같을 경우 true, 아니라면 false를 반환하는 문제이다.
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
nums.sort((a, b) => a - b);
let totalSum = nums.reduce((acc, cur) => acc + cur);
let target = totalSum / 2;
// 총합이 홀수라면 반으로 나눌 수 없으므로 false 반환
if (totalSum % 2 === 1) {
return false;
}
const backTracking = (current, index) => {
// target 값이 가능하면 true 반환
if (current === target) {
return true;
}
// 작은수부터 더해갔는데 target값을 넘거나,
// index가 범위를 넘었다면, 즉 다 돌아도 할 수 없다면 false 반환
if (current > target || index >= nums.length) {
return false;
}
// 현재값에 다음값을 더하고, 다음에 더할 수의 인덱스를 하나 더하던가,
// 다음값을 더했을 때 false 일 수 있으므로 현재값을 유지한채 다음에 더할 인덱스만 하나 더해줌
return (
backTracking(current + nums[index], index + 1) ||
backTracking(current, index + 1)
);
};
return backTracking(0, 0);
};
'PS > LeetCode' 카테고리의 다른 글
LeetCode / Tree / 100번 / Same Tree / JS (1) | 2023.05.14 |
---|---|
LeetCode / Two Pointer / 16번 / 3Sum Closese / JS (0) | 2023.05.14 |
LeetCode / Dynamic Programming / 322번 / Coin Change / JS (0) | 2023.05.14 |
LeetCode / Dynamic Programming / 198번 / House Robber / JS (0) | 2023.05.14 |