求生成数组中子数组所有唯一组合的算法方案

Hey there, let's break down how to solve this problem. You need to generate all unique non-empty combinations (subsets) of the subarrays in your main array, where combinations with the same subarrays in different orders aren't considered unique. That's exactly the classic "find all non-empty subsets" problem, and your example checks out—for 4 elements, there are 2⁴ - 1 = 15 unique non-empty subsets, which matches the list you provided.

Core Idea #

This problem boils down to finding all non-empty subsets of the main array. By definition, subsets are unordered collections of elements where each element is included at most once—perfectly aligning with your requirement that "subarrays in different orders don't count as unique combinations."

JavaScript Implementations #

Here are two straightforward, efficient ways to implement this:

Method 1: Iterative (Binary Mask Approach) #

We can use binary numbers to represent which elements are included in a subset. For an array of length n, each number from 1 to 2ⁿ - 1 (in binary) acts as a "mask"—each bit in the number tells us whether to include the corresponding element from the main array.

function generateUniqueSubsets(mainArray) {
  const subsets = [];
  const arrayLength = mainArray.length;
  
  // Iterate over all non-empty subsets (from 1 to 2^arrayLength - 1)
  for (let mask = 1; mask < (1 << arrayLength); mask++) {
    const currentSubset = [];
    for (let index = 0; index < arrayLength; index++) {
      // Check if the index-th bit in the mask is set to 1
      if (mask & (1 << index)) {
        currentSubset.push(mainArray[index]);
      }
    }
    subsets.push(currentSubset);
  }
  
  return subsets;
}

// Test with your example array
const mainArray = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]];
const allUniqueSubsets = generateUniqueSubsets(mainArray);
console.log(allUniqueSubsets);

Method 2: Recursive (Backtracking Approach) #

This approach builds subsets incrementally by choosing whether to include each element, and uses backtracking to avoid duplicate combinations (by only selecting elements after the current index, we skip permutations of the same subset).

function generateUniqueSubsets(mainArray) {
  const subsets = [];
  
  // Helper function for backtracking
  function backtrack(startIndex, currentSubset) {
    // Add non-empty subsets to the result
    if (currentSubset.length > 0) {
      subsets.push([...currentSubset]); // Create a copy to avoid reference issues
    }
    
    // Iterate from startIndex onward to avoid duplicate order combinations
    for (let i = startIndex; i < mainArray.length; i++) {
      currentSubset.push(mainArray[i]);
      backtrack(i + 1, currentSubset);
      currentSubset.pop(); // Backtrack: remove the last element to try the next one
    }
  }
  
  backtrack(0, []);
  return subsets;
}

// Test with your example array
const mainArray = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]];
const allUniqueSubsets = generateUniqueSubsets(mainArray);
console.log(allUniqueSubsets);

Verifying the Result #

Both methods will generate exactly the 15 unique subsets you listed in your example. The subsets are ordered based on the original array's element positions, but since we never generate permutations of the same subset (e.g., [[0.3,1], [0.5,2]] and [[0.5,2], [0.3,1]]), all combinations are unique as required.

内容的提问来源于stack exchange，提问作者Tim Nickels