Combination

def combination(arr):
    '''
    input: [a, b, c]
    output: [[]
            [a], [b], [c]
            [a, b], [a, c], [b, c]
            [a, b, c]]
    note: the order of the output does not matter.
    '''
    if not arr:
        return arr

    result = [[]]
    buff = []
    combination_helper(arr, 0, buff, result)
    return result

def combination_helper(arr, index, buff, result):
    # base case
    if index >= len(arr):
        return

    for i in xrange(index, len(arr)):
        buff.append(arr[i])
        result.append(list(buff))

        # recursion
        combination_helper(arr, i + 1, buff, result)

        buff.pop()

def combination_without_duplicates(arr):
    '''
    input: [a, b, c, c]
    output: [[]
            [a], [b], [c]
            [a, b], [a, c], [b, c], [c, c]
            [a, b, c], [a, c, c], [b, c, c]
            [a, b, c, c]]
    note: the order of the output does not matter.
          do not allow the duplicates in result.
    '''
    if not arr:
        return arr

    result = [[]]
    result_set = set([''])
    buff = []
    combination_without_duplicates_helper(arr, 0, buff, result, result_set)
    return result

def combination_without_duplicates_helper(arr, index, buff, result, result_set):
    # base
    if index >= len(arr):
        return

    for i in xrange(index, len(arr)):
        buff.append(arr[i])
        buff_str = ','.join(buff)
        if buff_str not in result_set:
            result_set.add(buff_str)
            result.append(list(buff))

            # recursion
            ## The reason why I do not put the 'recursion' outside of the 'if' statement is that
            ## if the set has cached the buff, which means this combination or part of combination
            ## has been processed, there is no need to do 'recursion' again. 
            combination_without_duplicates_helper(arr, i + 1, buff, result, result_set)

        buff.pop()

if __name__ == '__main__':
    arr_1 = ['a', 'b', 'c']
    result_1 = combination(arr_1)
    print result_1

    arr_2 = ['a', 'b', 'c', 'c']
    result_2 = combination_without_duplicates(arr_2)
    print result_2

Note:

• The time complexity = O(n!), n is the number of the elements in the given array.

• The space complexity = O\(n!\), n is the number of the elements in the given array.

• O(n!) > O(2 power of n), O(n!) is less efficient than O(2 power of n)

Combination formula

http://www.mathwords.com/c/combination\_formula.htm

'n choose r': The number of possible combinations from n choose r

Note: '阶乘' => 'Factorial'

       n! = n \* \(n - 1\) \* \(n - 2\) \* \(n - 3\) \* ... ... \* 1

For example:

n = 3, r = 2, the given set = ['a', 'b', 'c'], the number of possible combinations choosing 2 elements from the given set is 3

input: ['a', 'b', 'c']

output: ['a', 'b'], ['a', 'c'], ['b', 'c']