给定一个字符串 str，求该字符串的所有子集。由于是用字符串表示集合，所以空字符串表示空集，返回的结果中每个字符串不应出现重复字符。

示例 1:

Input: str = "ABC"
Output: ["", "A", "B", "C", "AB", "AC", "BC", "ABC"]

示例 2:

Input: str = "ABB"
Output: ["", "A", "B", "AB"]

解法

对于给定集合 str = "AB" ，我们可以把子集用固定长度的字符串表示（这里以下划线表示空字符串），得到 ["__", "A_", "_B", "AB"] 。在此基础上进行进一步抽象，使单个子集的元素序号与给定集合元素顺序一致，以 0 和 1 分别表示该元素在子集内不存在和存在，这样就可以用 ["00", "10", "01", "11"] 这样一组位图来表示子集。整个求解的过程可以看作以上解析的逆过程。

代码实现：

/**
 * 根据给定字符串，返回该字符串所有子集
 * @param {String} str 目标字符串
 * @returns {Array} subset 代表目标字符串所有子集的字符串数组
 */
function solution(str) {
  str = str || '';

  strArray = Array.from(new Set(str.split('')).values()); // 切分并去重

  const result = [];
  const max = 2 ** (strArray.length);

  for (let i = 0; i < max; i++) {
    let subsetStr = "";
    let bitmap = i; // 代表当前子集元素组成的位图

    // 从后往前逐位解析当前描述符代表的子集
    for (let j = strArray.length - 1; j >= 0; j--) {
      const shouldPick = bitmap % 2;
      bitmap = bitmap >> 1;

      subsetStr = shouldPick ? strArray[j] + subsetStr : subsetStr; // 如果当前位对应的元素存在，从目标集中取对应位的元素放入当前子集
    }

    result.push(subsetStr);
  }

  return result;
}


const assert = require('assert');
function uTest() {
  const testCases = [
    { input: '', expected: [''] },
    { input: 'A', expected: ['', 'A'] },
    { input: 'AA', expected: ['', 'A'] },
    { input: 'AB', expected: ['', 'B', 'A', 'AB'] },
    { input: '1231233334', expected: ['', '4', '3', '34', '2', '24', '23', '234', '1', '14', '13', '134', '12', '124', '123', '1234'] },
  ];

  for (let tc of testCases) {
    const actual = solution(tc.input);

    assert.deepEqual(actual, tc.expected, `For input ${tc.input} want ${tc.expected} but got ${actual}`);
  }

  console.log('Pass');
}
// uTest();