Intuitive | generating atmost 2 swaps with optimised recursion
IntuitionTry to use the generalised generate_atmost_swaps recursive function to generate almost equal numbers for a given number. Use the frequency of each numb
# Intuition
Try to use the generalised `generate_atmost_swaps` recursive function to generate almost equal numbers for a given number. Use the frequency of each number for counting number of almost equal pairs.

# Approach
I've got TLE when i used the recursive function directly so i tweaked it to prevent a few redundant generations and repeated swaps.
I used the `seen` set to store unique generations.
Do not forget to normalise each number to 7 digits by padding with `0`s (because each number <= `9999999` < `10^7`)


# Complexity
- Time complexity: $$O(n*7^2*maxSwaps)$$, here `maxSwaps` is 2

- Space complexity: $$O(n)$$, `n` is no. of unique permutations

# Code
```cpp []
class Solution {
public:
    unordered_map<string,int>freq;
    unordered_set<string>seen;
    void generate_atmost_swaps(string s,int swaps_left,int start_index){
        if(swaps_left<0)return;
        seen.insert(s);
        int n=s.size();
        for(int i=start_index;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(s[i]==s[j])continue;
                swap(s[i],s[j]);
                generate_atmost_swaps(s,swaps_left-1,i+1);
                swap(s[i],s[j]); // backtrack
            }
        }
    }

    int countPairs(vector<int>& nums) {
        int res=0;
        for(const int &x:nums){
            string num=to_string(x);
            while(num.size()<7)num='0'+num; // normalise to 7 digits
            res+=freq[num];
            seen.clear();
            generate_atmost_swaps(num,2,0);
            for(const auto &x:seen)freq[x]++;
            // cout<<num<<" "<<res<<endl;
        }
        return res;
    }
};
```
```python3 []
class Solution:
    def countPairs(self, nums: List[int]) -> int:
        freq=Counter()

        def generate_atmost_swaps(l,swaps_left,start_index=0):
            if swaps_left<0:return
            seen.add(''.join(l))
            n=len(l)
            for i in range(start_index,n):
                for j in range(i+1,n):
                    if l[i]==l[j]:continue
                    l[i],l[j]=l[j],l[i]
                    generate_atmost_swaps(l,swaps_left-1,i+1)
                    l[i],l[j]=l[j],l[i] # backtrack

        res=0
        for num in nums:
            num=str(num).zfill(7) # normalise to 7 digits
            res+=freq[num]
            seen=set()
            generate_atmost_swaps(list(num),2)
            for x in seen:freq[x]+=1
        return res
```

### Observations:
1. `C++` coders : You might get a TLE by passing set as a parameter to the generation function instead try global declaration and clear it using `setName.clear()` method or try reassigning it to an empty set or try `set<T>.swap(setName)`.
2. `Python` coders : You might get a TLE by passing string as a parameter instead consider using a list(reason: less number of str-to-list or list-to-str conversions, mutation friendly). Also consider reinitialising a set using `set()`->$$O(1)$$ instead of `setName.clear()`->$$O(n)$$.

### Note: 
- This solution is not a fully optimised one but i feed it as intuitive and beginner friendly. Feel free to share your views and optimisations.
['Hash Table', 'String', 'Recursion', 'String Matching', 'Combinatorics', 'Counting', 'Ordered Set', 'C++', 'Python3']