개선, 한 배열 에서 N 개의 수 를 찾 습 니 다. 그것 과 M 의 모든 가능성 을 찾 습 니 다.

이 는 본 고의 알고리즘 이 에서 N 개의 수 를 찾 아 낸 것 과 M 의 모든 가능성 인 가장 좋 은 해법 에서 바 뀌 었 다 는 것 을 설명 한다.본 고 는 서로 다른 것 은 이 진 정규 표현 법 을 사용 하 는데 이런 실현 방향 은 더욱 직관 적 이 고 간단 하 다 는 것 이다.
문제.
한 배열 에서 N 개의 수 를 찾 아 M 의 모든 가능성 을 찾 아 라.
예 를 들 어 배열 [1, 2, 3, 4] 에서 2 개의 요 소 를 선택 하여 5 의 모든 가능성 을 구한다.정 답 은 두 팀 의 조합 이다. 1, 4 와 2, 3.
패 키 징 함수 가 search 라 고 가정 합 니 다.

function search(arr, count, sum) {
    ...
    return res
}

있다

search([1,2,3,4],2,5)
// => [[2,3],[1,4]]

사고의 방향 을 실현 하 다.
여기 서 우 리 는 전체적인 방향 을 간단하게 말 합 니 다. 배열 의 길이 에 따라 바 이 너 리 데 이 터 를 구축 한 다음 에 그 중에서 조건 을 만족 시 키 는 데 이 터 를 선택 합 니 다.
우 리 는 배열 의 어떤 요소 가 선택 되 었 는 지 1 과 0 으로 표시 합 니 다.따라서 배열 의 1 위 와 2 위 가 뽑 혔 다 는 것 을 0110 으로 표시 할 수 있다.
길이 가 4 인 모든 바 이 너 리 데 이 터 를 열거 하여 상황 을 표시 합 니 다.

0000 은 배열 의 어떠한 요소 도 선택 하지 않 았 음 을 나타 낸다

0001 은 배열 의 3 위 요 소 를 선택 했다 고 밝 혔 다

.

0010 은 배열 의 두 번 째 요 소 를 선택 했다 고 밝 혔 다

.

0011 은 배열 의 2, 3 위 요 소 를 선택 했다 고 밝 혔 다

.

0100 은 배열 의 1 위 요 소 를 선택 했다 고 밝 혔 다

.

0101 은 배열 의 1, 3 위 요 소 를 선택 했다 고 밝 혔 다

.

0110 은 배열 의 1, 2 위 요 소 를 선택 했다 고 밝 혔 다

.

0111 은 배열 의 1, 2, 3 위 요 소 를 선택 했다 고 밝 혔 다

.

1000 은 배열 의 0 위 요 소 를 선택 했다 고 밝 혔 다

.

1001 은 배열 의 0, 3 위 요 소 를 선택 했다 고 밝 혔 다

.

1010 은 배열 의 0, 2 위 요 소 를 선택 했다 고 밝 혔 다

.

1011 은 배열 의 0, 2, 3 위 요 소 를 선택 했다 고 밝 혔 다

.

1110 은 배열 의 0, 1, 2 위 요 소 를 선택 했다 고 밝 혔 다

.

1111 은 배열 의 모든 비트 요 소 를 선택 했다 고 밝 혔 다

.
그러면 시작 하 는 예 는 4 선 2 로 조건 을 만족 시 키 는 바 이 너 리 는 0011, 0101, 0110, 1001, 1010, 1100 등 6 가지 가능성 이 있다.대응 요소 의 합 이 5 인 것 은 0110 과 1001 에 불과 하 다.
보 셨 습 니까? 사 고 는 우리 가 모든 길이 가 4 인 바 이 너 리 를 구축 하고 조건 에 맞 는 바 이 너 리 를 찾 는 것 입 니 다.
이곳 의 조건 은 두 가지 가 있다.

하 나 는 선 택 된 개수 가 2 이다.

둘 째 는 선 택 된 것 과 5 이다.

우리 의 알고리즘 사고방식 은 점점 뚜렷 해 졌 다. 모든 바 이 너 리 를 옮 겨 다 니 며 선택 한 개수 가 2 인지 아 닌 지 를 판단 한 다음 에 대응 하 는 요소 의 합 을 구하 고 5 인지 아 닌 지 를 보 자.
첫 번 째 문 제 는 어떻게 모든 바 이 너 리 데 이 터 를 옮 겨 다 닙 니까?
이것 은 우리 가 어렵 지 않 습 니 다. 배열 의 길이 가 4 이면 모든 바 이 너 리 데 이 터 는 0 - 15 입 니 다.

for (var i = 0; i < 16; i++) {
  ...
}

배열 길이 4, 대응 16, 즉 1 < 4.
주의 1 < 31 은 - 2147483648, Math. pow (2, 31) 로 대체 가능
두 번 째 문 제 는 선택 한 요소 의 개 수 를 어떻게 구 합 니까?바 이 너 리 문자열 중 1 의 개 수 를 구 하 는 것 입 니까?
실현 방식 은 여러 가지 가 있다. 예 를 들 어 그 중의 하 나 는:

function n(i) {
  var count = 0;
  while( i ) {
   if(i & 1){
    ++count;
   }
   i >>= 1;
  }
  return count;
}
console.log(n(0b1010))
// => 2

상술 한 알고리즘 의 사고방식 은 사실 매우 간단 하 다. 이 진 을 점차적으로 오른쪽으로 한 자리 옮 겨 서 끝 이 1 인 개 수 를 보 자.예 를 들 어 10 의 이 진 은 1010 이 고 점차적으로 오른쪽으로 이동 하 는 모든 것 은 1010 - > 101 - > 10 - > 1 - > 0 일 수 있 으 며 그 중에서 2 번 의 끝 은 1 이다.그래서 결 과 는 2.
세 번 째 문 제 는 어떻게 이 진 데이터 에 근거 하여 화 해 를 구 합 니까?
예 를 들 어 0110, 우 리 는 arr [1] + arr [2] 를 구 해 야 한다.
문 제 는 배열 의 하 표 가 0110 에 있 는 지 아 닌 지 를 어떻게 판단 하 느 냐 로 바 뀌 었 다.
사실은 매우 간단 하 다. 예 를 들 어 아래 표 시 는 1 이 있 고 아래 표 시 는 3 이 없다.우 리 는 1 을 0100, 0110 & 0100 으로 0 보다 크 기 때문에 아래 표 시 는 1 에 있다.0110 & 0001 은 0 이기 때문에 아래 표 시 는 3 이 없습니다.
그래서 우 리 를 구 하 는 것 은 다음 과 같다.

var arr = [1,2,3,4]
var s = 0, temp = [];
for (var i = 0, len = arr.length; i < len; i++) {
  if ( 0b0110 & 1 << (len - 1 - i)) {
	s += arr[i]
	temp.push(arr[i])
  }
}
console.log(temp)
// => [2,3]

최종 실현
이상 의 깔개 가 있 으 면 여기 서 최종 실현 을 제시 합 니 다.

function search(arr, count, sum) {
  var len = arr.length, res = [];
  for (var i = 0; i < Math.pow(2, len); i++) {
	if (n(i) == count) {
	  var s = 0, temp = [];
	  for (var j = 0; j < len; j++) {
		if (i & 1 << (len - 1 -j)) {
		  s += arr[j]
		  temp.push(arr[j])
		}
	  }
	  if (s == sum) {
		res.push(temp)
	  }
	}
  }
  return res;
}

function n(i) {
  var count = 0;
  while( i ) {
   if(i & 1){
    ++count;
   }
   i >>= 1;
  }
  return count;
}

console.log(search([1,2,3,4],2,5))
// => [[2,3],[1,4]]

마지막 으로 각종 개념 을 도입 하지 않 아 도 이 알고리즘 을 분명하게 말 할 수 있 음 을 알 수 있다.
본문 이 끝나다.