Finding the indices of the two items whose price adds up to to a value I've solved the Google Jam store credit problem. but there's some inefficiencies that I want to get rid of them to improve the algorithm and reduce the multiple iteration. What are other better ways to do so?

Problem:


  You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).
  
  Input:
  
  The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:
  
  
  One line containing the value C, the amount of credit you have at the
  store.
  One line containing the value I, the number of items in the
  store.
  One line containing a space separated list of I integers. Each
  integer P indicates the price of an item in the store.
  Each test case
  will have exactly one solution.
  
  
  Output:
  
  For each test case, output one line containing "Case #x: " followed by
  the indices of the two items whose price adds up to the store credit.
  The lower index should be output first.
  
  Limits
  
  5 ≤ C ≤ 1000 1 ≤ P ≤ 1000
  
  Small dataset
  
  N = 10 3 ≤ I ≤ 100
  
  Large dataset
  
  N = 50 3 ≤ I ≤ 2000


Solution:

#!/usr/bin/env python3.4
import sys
from itertools import combinations, count

cases = []
credits = []
items = []

with open(sys.argv[1]) as file_:
    next(file_)
    cases = (list(zip(*[file_]*3)))

for case in cases:
    credits.append(int(case[0]))
    items.append([int(item) for item in case[2].split()])

for credit, prices, i in zip(credits, items, count()):
    for tow_items in combinations(prices, 2):
        if sum(tow_items) == credit:
            print("Case #{}:".format(i+1), end=' ')
            print(' '.join([str(i+1) for i, price in enumerate(prices)
                            if price in tow_items]))
Code organisation

Instead of building cases, then use it to build credits and items then use them to fix the problem, you could do things in a more straightforward way with less temporary containers.

with open(sys.argv[1]) as file_:
    next(file_)
    for i, case in enumerate(zip(*[file_]*3)):
        credit = int(case[0])
        prices = [int(item) for item in case[2].split()]
        for tow_items in combinations(prices, 2):
            if sum(tow_items) == credit:
                print("Case #{}:".format(i+1), end=' ')
                print(' '.join([str(i+1) for i, price in enumerate(prices) if price in tow_items]))


Also, it would probably make sense to split your code into multiple functions : you could write a function handling input/ouput and a function to handle the algorithmic part of the problem.

def get_indices_with_sum(prices, credit):
    for tow_items in combinations(prices, 2):
        if sum(tow_items) == credit:
            return [i for i, price in enumerate(prices) if price in tow_items]
    assert False  # Is not suppose to happen

def run_on_file(filename):
    with open(filename) as file_:
        next(file_)
        for i, case in enumerate(zip(*[file_]*3)):
            credit = int(case[0])
            prices = [int(item) for item in case[2].split()]
            j, k = get_indices_with_sum(prices, credit)
            print("Case #{}: {} {}".format(i+1, j+1, k+1))

run_on_file(sys.argv[1])


Now, different great things are easily doable :
 - you can your call to run_on_file behind an if __name__ == "__main__": guard to have reusable code on one hand (you could need the get_indices_with_sum function to solve other problems) and code actually doing something on the other hand.
 - you can write tests to check your code automatically. The great thing is that the problem description gives you a few examples.

def unit_tests():
    j, k = get_indices_with_sum([5, 75, 25], 100)
    assert (j, k) == (1, 2)
    j, k = get_indices_with_sum([150, 24, 79, 50, 88, 345, 3], 200)
    assert (j, k) == (0, 3)
    j, k = get_indices_with_sum([2, 1, 9, 4, 4, 56, 90, 3], 8)
    assert (j, k) == (3, 4)


if __name__ == "__main__":
    unit_tests()
    # run_on_file(sys.argv[1])


At this step, your code is already better but we haven't improved performance. We've only make improvements easier to write and to test.

Algorithm

In order to write a faster algorithm, I am assuming we are interested in the case when we are given a store with a huge number of elements n (called I in the problem description).

At the moment, you (potentially) iterate over all combinations and there are n * (n-1)/2. Assuming you always find what you are looking for, we may assume that you go through n * (n-1) / 4 combinations in average. Then, when the solution is found, your iterate once more over prices so you roughly perform n + n * (n-1) / 4 operations. We usually keep only the asymptotic behavior of the program and remove the constant factor and say that your program is 'O(n^2)'.

You could try to run your program with bigger and bigger inputs and see the time it takes. Usually when you take a input twice as big, your algorithm will take 4 times as much time.

If you want to give it a try, I've tweaked the original test to add the following cases (adding elements costing 101 in the store doesn't change what you can get with 100 dollars):

nb_added_elements = 10000
j, k = get_indices_with_sum([101] * nb_added_elements + [5, 75, 25], 100)
assert (j, k) == (nb_added_elements + 1, nb_added_elements + 2)
j, k = get_indices_with_sum([5, 75, 25] + [101] * nb_added_elements, 100)
assert (j, k) == (1, 2)


The problem you are trying to solve is pretty common and has a O(n) solution on a sorted array (you'll find explanations looking for "array find pair sum" in our favorite search engine).

Your case is slightly more complicated because the array is not sorted and sorting it would cause a mess in the indices.

Many solutions are possible : either build an array with value and index before sorting it by value and/or keep a copy of the unsorted array so that you can find its initial position back at the end.

The resulting solution is likely to be O(n*log(n)) because of the sorting (other operations such as lookup/copy and obviously the proper algorithm are only O(n) and as such considered negligeable).

Other details

count and enumerate can be given a starting position (defaulting to 0) so that you don't have to add 1 yourself if you want to count from 0.