Leetcode - 78. Subsets

문제

배열에 주어진 숫자로 만들 수 있는 모든 조합을 리턴하라.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

해결

0 개부터 n(배열갯수)개 까지 각각의 수를 선택할수 있는 조합(Combination)을 백트래킹을 통해 구한다.

class Solution {
    vector<vector<int>> ret;
    vector<int> tmp;
    int nsize;
    
    void back_tracking(vector<int> nums, int cur, int tgt) {
        if (tgt < 0)
            return;
        if (tgt == 0) {
            ret.push_back(tmp);
            return;
        }
        for (int i = cur; i < nsize; i++) {
            tmp.push_back(nums[i]);
            back_tracking(nums, i + 1, tgt - 1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        nsize = nums.size();
        for (int i = 0; i <= nsize; i++) {
            back_tracking(nums, 0, i);
        }
        return ret;
    }
};