Pairs from an array

Input

[1,2,3,4]

Output

[(1, 2), (3, 4)]
[(1, 3), (2, 4)]
[(1, 4), (2, 3)]

Key ideas

• We want to generate combinations from the input, and we don't know how many combinations there are -> this is a hint to use the backtracking strategy
• When we pick a number, we mark the selection, so we won't pick the same number again -> I am gonna use HashMap to mark it.
• Because HashMap is passed by reference, we need to copy the current status before selecting a number, so that
  • the selection status will not be messed up by the next recursion
  • we can reuse the status when we need to run recursion from this level again

def main(nums):
    total_pairs = []
    num_length = len(nums)
    possible_indices = {}
    for i in range(num_length):
        possible_indices[i] = True

    def compose(possible_indices, pairs):
        # ending condition
        if len(pairs) == num_length / 2:
            total_pairs.append(pairs)
            return

        # compose
        # fix i, find j:
        _possible_indices = possible_indices.copy()
        for i in range(num_length):
            if _possible_indices[i]:
                _possible_indices[i] = False
                break

        for j in range(num_length):
            if _possible_indices[j]:
                _pairs = pairs.copy()
                __possible_indices = _possible_indices.copy()
                __possible_indices[j] = False
                _pairs.append((nums[i], nums[j]))
                compose(__possible_indices, _pairs)

    compose(possible_indices, [])

Time complexity: We run compose() in a for loop. Even though the actual number of times we run compose() decreases by 2(because 2 numbers are marked as selected) in each recursion. The upper bound would still factorial: O(n!)

Space complexity: possible_indices itself makes space complexity O(n). We copy it twice in each recursion, making overall space complexity O(2*n*n!), amortized O(n*n!)