[LeetCode] 282. Expression Add Operators

문제 URL : https://leetcode.com/problems/expression-add-operators/

Expression Add Operators - LeetCode

 

문제 접근법:  숫자와 숫자 사이에 연산자를 집어 넣어서 계산결과가 target을 만들어내는 알고리즘문제입니다.

 

모든 경우의수를 다 구하면 되기때문에 재귀함수를 이용하면 됩니다. 단 숫자를 만들때 앞에 0이되는숫자는 제외해야합니다.

 

소스코드 :

class Solution {
public:
vector<string> res;
string s;
void dfs(string &num,int target,long long before,long long sum,int idx){
    if(idx>=num.size()){
        if(sum==target){
            res.push_back(s);
        }
        return;
    }
    for(int i=idx;i<num.size();i++){
        string temp =num.substr(idx,i-idx+1);
        if(temp.size()>1&&temp[0]=='0')break;
        long long number = stoll(temp);
        s+='+';
        s+=temp;
        dfs(num,target,number,sum+number,i+1);
        s[s.size()-temp.size()-1]='-';
        dfs(num,target,-number,sum-number,i+1);
        s[s.size()-temp.size()-1]='*';
        dfs(num,target,before*number,sum-before+before*number,i+1);
        s.erase(s.begin()+s.size()-temp.size()-1,s.end());
    }

}
vector<string> addOperators(string num, int target) {
    for(int i=0;i<num.size();i++){
        string temp=num.substr(0,i+1);
        if(temp.size()>1&&temp[0]=='0')break;
        long long number = stoll(temp);
        s+=temp;
        dfs(num,target,number,number,i+1);
        for(int j=0;j<temp.size();j++)s.pop_back();
    }
    return res;
}
};

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.