[java script] 조합

n개의 수 중에서 x개를 뽑아 더해서 만들 수 있는 수 중에서 가장 큰 수를 찾기.

 

1) 재귀

//조합   n개의 수 중에서 x개를 뽑아 더해서 만들 수 있는 수 중에서 가장 큰 수를 찾기.
    let nums=[1,2,3,4]; 
    let x = 2 ; 
    let n = nums.length; 
    function solve(pos, cnt, val){ 
      if(cnt==x) return val; 
      if(pos==n) return -1; 

      let max = 0; 
      let temp; 

      temp = solve(pos+1,cnt+1, val+nums[pos]); 
      if(temp>max) max = temp; 

      temp = solve(pos+1,cnt, val); 
      if(temp>max) max = temp;

      return max; 
    }

    answer = solve(0,0,0); 

    console.log(answer); 

 

2)반복  bit 연산을 통해 부분집합을 만들어 반복한다. 

  //조합   n개의 수 중에서 x개를 뽑아 더해서 만들 수 있는 수 중에서 가장 큰 수를 찾기. (bit)
    let nums=[1,2,3,4]; 
    let x = 2; 
    let n = nums.length; 
    
    function countBits(value){ 
      let count  = 0; 
      while(value>0){ 
        if((value&1)==1) count++; 
        value = value>>1; 
      }
      return count; 
    }

    function solve(){ 
      let max = 0; 
      for( let i  = 0; i<(1<<n); i++){ 
        if(countBits(i)==x){ 
          let sum =0; 
          for( let j=0; j<n; j++){ 
            if(i&(1<<j)) sum+=nums[j]; 
          }
          if(sum>max) max = sum; 
        }
      }
      return max; 
    }



    answer = solve(); 

    console.log(answer); 

 

 

선택의 순서가 결과에 영향을 주지 않는 경우에는 조합을 이용한다.