תיאור השאלה
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and the subsets can be returned in any order.
איך פותרים?
Backtracking: כל מצב ברקורסיה הוא תת־קבוצה חוקית ולכן שומרים אותו מיד. אחר כך מנסים להוסיף כל איבר שבא אחרי האיבר האחרון שנבחר. יש 2ⁿ תתי־קבוצות, ולכן הסיבוכיות היא O(n·2ⁿ).
פתרון קוד
JavaScript
Python
function subsets(nums) {
const result = [];
const current = [];
function backtrack(start) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
}
backtrack(0);
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.