[leetcode] 18. 4Sum

class Solution {
public:
    
    vector<vector<int>> answer;

    void check(vector<int>& nums, int target, int now, int cnt, int sum, vector<int>& path){
        if(cnt == 4){
            if(sum == target) answer.push_back(path);
            return;
        }
        
        for(int i = now + 1; i<nums.size(); i++){
            path.push_back(nums[i]);
            check(nums, target, i, cnt + 1, sum + nums[i], path);
            path.pop_back();
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        check(nums, target, -1, 0, 0, path);
        
        sort(answer.begin(), answer.end());
        answer.erase(unique(answer.begin(), answer.end()), answer.end());
        
        return answer;
    }
};

 

제일 간단하게 BF로 먼저 풀어보았습니다. 

극악의 복잡도네요. 운좋게도 간당간당하게 통과시켜주네요

시간복잡도 : O(n^4)

더 좋은 방법이 뭐가 잇을지 고민해보도록 하죠

 

 

 

[추가]

다른분들의 풀이를 보니 2중 fot문에 2포인터 기법으로 푸시던데,,

속도차이 좀 나긴하지만 직관적이고 깔끔한 제 풀이로 만족하려합니다.