인프런 커뮤니티 질문&답변

질문 그대로 입니다. 두 부분집합이 서로소 인 경우는 최대공약수가 1인 경우인데요.

처음 찾은 부분집합이[1,3,5,7] - [6,10]이면 상관없는데 [1,5,10] - [3,6,7] 일경우 서로소 집합이 아닌데도(10 - 6은 서로소가 아니므로 서로소집합이 아니라고 생각합니다) 바로 빠져나가버려서 서로소집합이 아닌 경우에도 yes가 출력될 수 있습니다.

  따라서 ,부분 집합의 합이 서로 같을 경우에 그 다음으로 서로소를 판별하는 과정이 있어야 한다고 생각합니다.

그래서 조금은 길지만 코드를 짜보았습니다!

 function subsetSum(arrLength, set) {
        let result = [];
        let answer = [];
        let tmpArr = [];
        let found = false;
        let sum = set.reduce((a, b) => a + b);

        function compareTwoNum(a, b) {
          let smaller = a > b ? b : a;
          for (let i = 2; i < smaller; i++) {
            let conditionOne = a % i === 0;
            let conditionTwo = b % i === 0;
            if (conditionOne && conditionTwo) {
              return false;
            }
          }
          return true;
        }

        function isRelativePrimeSets(arr, arr2) {
          for (let i = 0; i < arr.length; i++) {
            for (let j = 0; j < arr2.length; j++) {
              if (compareTwoNum(arr[i], arr2[j])) continue;
              else return false;
            }
          }

          return true;
        }

        function dfs(num, set) {
          if (found) return;
          if (num > arrLength - 1) {
            for (let i = 0; i < result.length; i++) {
              if (result[i] === 1) tmpArr.push(set[i]);
            }
            // console.log(tmpArr);
            if (
              tmpArr.length > 0 &&
              tmpArr.reduce((a, b) => a + b) * 2 === sum
            ) {
              let theOther = set.filter(function (e) {
                return this.indexOf(e) < 0;
              }, tmpArr);
              if (isRelativePrimeSets(tmpArr, theOther)) {
                answer.push(tmpArr);
                found = true;
              }
            }
            // if (tmpArr.length > 0) answer.push(tmpArr);
            tmpArr = [];
            return;
          } else {
            result[num] = 1;
            dfs(num + 1, set);
            result[num] = 0;
            dfs(num + 1, set);
          }
        }

        dfs(0, set);
        return answer;
      }

subsetSum(6,[ 1, 3, 5, 6, 7, 10]) // [1, 3, 5, 7]

정말 말그대로 isrelativePrimeSets()을 통해서 하나하나 다 판별한다음 모두 서로소이면 탐색중지(found = true) 아님 계속 탐색하는 식으로  코드를 짜보았습니다!

예를들어 [ 1, 3, 4, 6, 7, 13] 가 주어진 경우 선생님 코드로 실행하게 되면 [1,3,6,7]-[4,13] 이 나오지만 제 코드로 실행하면 [1,3,13]-[4,6,7] 이 나오게 됩니다.