Go O(n) 100% - No Sorting - Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n## Observation 1: Count The Non-Beautiful Subsets\nGiven some set, A, the power set, \m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n## Observation 1: Count The Non-Beautiful Subsets\nGiven some set, $$A$$, the power set, $$\\mathcal{P} (A)$$, is the set containing all subsets of $$A$$ including the empty set, $$\\{\\}$$, and itself. For example,\n\n$$\\mathcal{P} (\\{1,2,3\\})=\\{\\{\\}, \\{1\\},\\{2\\},\\{3\\},\\{1,2\\},\\{1,3\\}\\{2,3\\}, \\{1,2,3\\}\\}$$\n\nWe can partition the power set into two subsets: $$\\mathcal{P} (A)_{b}$$, all beautiful subsets, and $$\\mathcal{P} (A)_{n}$$, all non-beautiful subsets. Rather than counting the number of beautiful subsets directly, we can count the number of non-beautiful subsets and subtract that from the total number of subsets. Expressed succinctly, where $$|S|$$ denotes the *cardinality* (i.e. number of elements) of a set,\n\n$$|\\mathcal{P} (A)|=|\\mathcal{P} (A)_{b}|+|\\mathcal{P} (A)_{n}| \\implies |\\mathcal{P} (A)_{b}|=|\\mathcal{P} (A)|-|\\mathcal{P} (A)_{n}|$$\n\nAs it turns out, $$|\\mathcal{P} (A)| = 2^{|A|}$$, or, put simply, the number of unique subsets you can create from any set is equal to two to the power of the number of elements in that set, so the above expression becomes:\n\n$$|\\mathcal{P} (A)_{b}|=2^{|A|}-|\\mathcal{P} (A)_{n}|$$\n\nNow the question becomes, how do I calculate the number of non-beautiful subsets, $$|\\mathcal{P} (A)_{n}|$$?\n\n## Observation 2: Building Non-Beautiful Subsets\nA *multiset* is a set that allows for more than one instance of an element. The number of occurrences of an element in a multiset is referred to as its *multiplicity*. Expressed in explicit form, each element in a multiset can be given a superscript to denote its multiplicity (e.g. $$\\{1^2, 5^3\\}=\\{1,1,5,5,5\\}$$). The multiplicity of element $$e$$ in set $$S$$ can also be expressed as $$m_S (e)$$.\n\nConsider a multiset, $$S$$, to which we want to add a new element, $$e_i$$.\n\n$$\nS=\\{e_1^{m(e_1)},e_2^{m(e_2)},...,e_{i-1}^{m(e_{i-1})}\\}\n$$\n\nGiven the precondition that $$e_i+k \\notin S$$ we can express$$|\\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n}|$$ in terms of $$|\\mathcal{P} (S)_{n}|$$ and $$|\\mathcal{P}(S-\\{(e_i-k)^{m_S (e_i-k)}\\})_n|$$ (*note this isn\'t an exponent, it\'s the multiplicity of $$e_i-k$$*).\n\nWe can partition $$\\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n}$$ into three subsets:\n\n1. $$\\mathcal{P} (S)_{n}$$, subsets that do not contain $$e_i$$.\n2. $$A_{both}=\\{ X \\, : \\, X \\in \\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n} \\quad \\textrm{and} \\quad  e_i \\in X \\quad \\textrm{and} \\quad e_i-k \\in X\\}$$, subsets that contain both $$e_i$$ and $$e_i - k$$.\n3. $$A_{one}=\\{ X \\, : \\, X \\in \\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n} \\quad \\textrm{and} \\quad  e_i \\in X \\quad \\textrm{and} \\quad e_i-k \\notin X\\}$$, subsets that contain $$e_i$$ but not $$e_i-k$$.\n\nIf we know the cardinality of each of these sets then we know $$|\\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n}|$$, because $$|\\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n}|=|\\mathcal{P} (S)_{n}|+|A_{both}|+|A_{one}|$$.\n\nNotice that as long as a set includes $$e_i$$ and $$e_i-k$$ it is a non-beautiful set. We can reason that for any combination of $$e_i$$ and $$e_i-k$$ there are $$|\\mathcal{P}(S-\\{(e_i-k)^{m_S (e_i-k)}\\})|$$ subsets in $$A_{both}$$. There are $$(2^{m_S (e_i-k)}-1)(2^{m (e_i)}-1)$$ such combinations, so\n\n$$\n|A_{both}|=(2^{m_S (e_i-k)}-1)(2^{m (e_i)}-1)(2^{|S|-m_S (e_i - k)})\n$$\n\nAlso notice that if a set, $$X$$, includes $$e_i$$ but does not include $$e_i-k$$ it can only be a non-beautiful subset if $$X-\\{e_i^{m_X (e_i)}\\} \\in \\mathcal{P}(S-\\{(e_i-k)^{m_S (e_i-k)}\\})_n$$. Therefore,\n\n$$\n|A_{one}|=(2^{m(e_i)}-1)|\\mathcal{P}(S-\\{(e_i-k)^{m_S (e_i-k)}\\})_n|\n$$\n\nso,\n\n$$\n\\begin{align}\n|\\mathcal{P} (S \\cup \\{e_i^{m(e_i)}\\})_{n}| \n  &= |\\mathcal{P} (S)_{n}|+|A_{both}|+|A_{one}| \\\\\n  &= |\\mathcal{P} (S)_{n}|\n     +|\\mathcal{P}(S-\\{(e_i-k)^{m_S (e_i-k)}\\})_n|(2^{m(e_i)}-1)\n     +(2^{m_S (e_i-k)}-1)(2^{m (e_i)}-1)(2^{|S|-m_S (e_i - k)})\n\\end{align}\n$$\n\nIf $$S=\\{\\}$$, it\'s clear to see that $$|\\mathcal{P} (S)_{n}|=0$$. If we add one element at a time to $$S$$ we can keep track of the number of non-beautiful sets inductively using the above expression. In order to maintain the invariant it is sufficient to ensure that for each "chain" of numbers, we add the numbers in ascending order. In other words, we always add $$i$$ before adding $$i+k$$.\n\n## Observation 3: Forming Chains\nWe can break apart a set, $$S$$, into several *chains* where each chain is a sequence of numbers that are $$k$$-apart. For example, if $$S=\\{1,1,2,3,5,6,9,10\\}$$ and $$k=1$$, then we can form three chains: $$\\{1,1,2,3\\}$$, $$\\{5,6\\}$$, and $$\\{9,10\\}$$. We can process these chains in any order as long as we add the elements in a particular chain in ascending order. One way we can represent this is as a mapping between number and occurrences:\n\n$$\nS=\\{1:2,\\;2:1,\\;3:1,\\;5:1,\\;6:1,\\;9:1,\\;10:1\\}\n$$\n\nWe can traverse any chain by picking an arbitrary element, $$i$$, and checking for the existence of $$S[i-k]$$ and $$S[i+k]$$. $$S[i]$$ tells us the multiplicity of the set element (i.e. $$m_S(i)$$).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Convert `nums` to a `map[int]int` that maps number to number of occurrences.\n2. For each chain, find the first element then traverse forward through the chain keeping track of the non-beautiful subsets using the formula above. Add one at the end to account for the empty set.\n3. Return `2^len(nums)-non_beautiful_subsets`\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunc beautifulSubsets(nums []int, k int) int {\n    return pow(len(nums)) - nonBeautifulSubsets(nums, k)\n}\n\nfunc nonBeautifulSubsets(nums []int, k int) int {\n    m := map[int]int{} // m[i] = multiplicity of element i\n    for _, n := range nums {\n        m[n]++\n    }\n\n    var total [3]int // non-beautiful subsets found so far\n    var sSize int    // size of set S so far\n\n    for i := range m {\n        i = min(i, k, m)\n\n        // Traverse chain\n        for ; m[i] != 0; i, sSize, total = i+k, sSize+m[i], shift(total) {\n            aOne := pow(m[i]) - 1\n\n            // If this is the first in its chain, then P(S-{i-k}) = P(S),\n            // so we need to multiply by total[1], as this represents |P(S)|.\n            // Otherwise, we need to multiply by what total was before\n            // adding element {i-k}, so we use total[2].\n            if m[i-k] == 0 {\n                aOne *= total[1]\n            } else {\n                aOne *= total[2]\n            }\n\n            // Basically our formula from the solution.\n            total[0] = total[1] + aOne + (pow(m[i]) - 1)*(pow(m[i-k]) - 1)*pow(sSize-m[i-k])\n\n            // Delete m[i-k] so it won\'t be reprocessed.\n            delete(m, i-k)\n        }\n\n        // Delete m[i-k] so it won\'t be reprocessed.\n        delete(m, i-k)\n    }\n\n    // +1 because we can\'t forget the empty set!\n    return total[0] + 1\n}\n\nfunc pow(n int) int {\n    return 1 << n\n}\n\nfunc min(i int, k int, hist map[int]int) int {\n    if hist[i] == 0 {\n        return i+k\n    }\n    \n    return min(i-k, k, hist)\n}\n\nfunc shift(total [3]int) [3]int {\n    total[1], total[2] = total[0], total[1]\n\n    return total\n}\n```
['Go']