描述

从数组 Arr[1…m] 中任选 n 个元素的所有组合, 无顺序.

实现

  2. // 假设有以下数组 arr, m = 3, n = 2; 即从长度为 3 的数组里得到两两组合的结果.
  3. const arr = [ 'A', 'B', 'C' ];
  5. // 最大组合情况为 `ABC`, 用二进制表示, 临界值为 111b, < 1000b, 即向左位移 m 位
  6. const i = 1 << arr.length;
  9. // 第一层循环，求出对应上一步小于 i 的全部组合，例如001b,010b,011b,100b,101b,110b,111b
  10. for (let p = 1; p < i; p++) { 
  12.   let k = 0; // 记录找到的 1 的下标
  13.   let cnt = 0; // 记录找到多少个1
  14.   let result = [];
  16.   // 第二层循环, 求出上面其中一个组合中有多少个1，找到每个1的对应下标，
  17.   // 例如110，则 result[0] = arr[1]; result[1] = arr[2]; 对应 arr 中的元素，也就是 B、 C;
  18.   for (let q = p; q !== 0; q = q >> 1){
  19.     k++;
  20.     if (q&1 === 1) { // 1 位
  21.       cnt++;
  22.       result.push(arr[ k - 1 ]);
  23.       if (k > 2) break; // 剪枝， 超过 n 个1，跳出内层循环
  24.     }
  25.   }
  26.   if (cnt === 2) { // 找到长度为 2 的组合
  27.     console.log(result); // AB, AC, BC
  28.   }
  29. }

上面的方法，时间复杂度为 (1<<m)*m .

递归实现

  1. const arr = [ 'A', 'B', 'C' ];
  2. const n = 2;
  3. const result = [];
  5. const Combine = k =>  {
  7.     if (k > arr.length - 1){
  8.         // 找到长度为 n 的组合
  9.         const tmp = [];
  10.         for( let i = 0; i < result.length; i++ ) {
  11.             if (result[i].length === n) {
  12.                 tmp.push(result[i]);
  13.             }
  14.         }
  15.         return tmp;
  17.         // return result; // result 在不剪枝情况为全组合结果
  18.     }
  19.     const leng = result.length;
  20.     for (let i = 0; i < leng; i++) {
  21.         if (result[i].length < n) { // 剪枝，取 n
  22.             result.push(arr[k] + result[i]);
  23.         }
  24.     }
  25.     result.push(arr[k]); // 要把 arr[k] 也 push 进去给下一次递归组合
  26.     return Combine(k+1);
  27. }
  28. Combine(0); // ["BA", "CA", "CB"]