תיאור השאלה
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets.
איך פותרים?
כמו ב־Subsets, אבל קודם ממיינים. בתוך אותה רמת רקורסיה מדלגים על מספר ששווה לקודם לו, כי הוא ייצור בדיוק את אותן תתי־קבוצות. סיבוכיות: O(n·2ⁿ).
פתרון קוד
JavaScript
Python
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [];
const current = [];
function backtrack(start) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
}
backtrack(0);
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.