Intuition

배열을 순회하며 각 원소마다 +인 경우와 -인 경우를 모두 확인한다.

Approach&Solution

int cnt;

void targetSum(int* nums, int numsSize, int target, int sum, int idx){
    if (idx==numsSize){
        if(target==sum) cnt++; // 하나의 sequence를 완성하면, targetSum과 일치하는지 확인
    }
    else{ // +인 경우와 -인 경우 각각의 계산결과를 매개변수로 넘김
        targetSum(nums,numsSize,target,sum+nums[idx],idx+1);
        targetSum(nums,numsSize,target,sum-nums[idx],idx+1);
    }
}

int findTargetSumWays(int* nums, int numsSize, int target) {
    cnt=0;
    targetSum(nums,numsSize,target,0,0);
    return cnt;
}

Time Complexity

$\therefore O(2^n)$

지적 및 질문 환영