The problem goes like this:
You are given an integer array nums.
A nice permutation is defined as a permutation of any non-empty subset of nums such that the absolute difference between any two consecutive elements is exactly 1. A permutation of size 1 is considered nice by definition. A subset is any non-empty selection of elements from nums (regardless of order). A permutation of a subset is any reordering of the elements of a subset.
Your task is to compute the sum of all elements across all such nice permutations.
Since the total may be very large, output the result modulo $$$10^9 + 7$$$.
Input
- An array
numsof integers. - $$$1 \leq \text{nums.length} \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)
- $$$0 \leq \text{nums}[i] \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)
Output
- A single integer: the sum of all elements in all nice permutations of all non-empty subsets of
nums, taken modulo $$$10^9 + 7$$$.
Examples
nums = [1, 2, 3]
[1],[2],[3],[1,2],[2,1],[2,3],[3,2],[1,2,3],[3,2,1]are all valid.- The sum is 34.
[1, 3],[3, 1],[2,3,1],[2,1,3],[3,1,2], and[1,3,2]are not valid.
nums = [2, 3, 2]
[2],[2],[3],[2,3],[3,2],[2,3],[3,2],[2,3,2],[2,3,2]are all valid.- The sum is 41.
[2,2],[2,2],[2,2,3],[2,2,3],[3,2,2], and[3,2,2]are not valid.
Apart from brute-forcing all $$$\sum_{k=1}^{n} \binom{n}{k} \cdot k!$$$ possibilities, I can't find any way to do it. I feel like we should start by sorting and making clusters (for example [1, 2, 9, 10, 11, 12] would have two clusters, [1, 2] and [9, 10, 11, 12]), but that kind of got me nowhere.
